说明

本题要求计算邮递员遍历所有街道至少一次并返回起点的最小费用。关键在于利用欧拉路径和弗洛伊德算法处理奇数度节点，确保路径最短。

算法标签

• 图论：处理街道和交叉口的图结构
• 欧拉路径：判断是否存在欧拉回路或路径
• 弗洛伊德算法：计算所有交叉口之间的最短路径
• 贪心算法：选择最优路径组合

解题思路

1. 问题分析：

   • 邮递员需要遍历所有街道至少一次并返回起点。
   • 街道的费用由名称长度决定。
   • 最多有两个奇数度交叉口，其他均为偶数度。

2. 关键步骤：

   • 统计每个交叉口的度数。
   • 计算所有街道的总长度。
   • 若存在两个奇数度交叉口，计算它们之间的最短路径并加到总长度中。
   • 若所有交叉口均为偶数度，直接输出总长度。

3. 算法选择：

   • 使用弗洛伊德算法预处理所有交叉口之间的最短路径。
   • 根据欧拉路径的性质决定是否需要额外路径。

分析

1. 输入处理：

   • 读取街道名称，统计交叉口度数和街道长度。
   • 构建邻接矩阵，记录交叉口之间的距离。

2. 弗洛伊德算法：

   • 计算所有交叉口之间的最短路径，存储在邻接矩阵中。

3. 欧拉路径判断：

   • 统计奇数度交叉口数量。
   • 若有两个奇数度交叉口，找到它们之间的最短路径并累加。

4. 结果输出：

   • 输出最小旅行费用。

实现步骤

1. 初始化：

   • 邻接矩阵初始化为无穷大。
   • 度数数组初始化为0。

2. 处理输入：

   • 读取街道名称，更新邻接矩阵和度数数组。
   • 累加所有街道长度到总费用。

3. 弗洛伊德算法：

   • 三重循环更新最短路径。

4. 处理奇数度节点：

   • 若存在两个奇数度节点，找到它们之间的最短路径并累加。

5. 输出结果：

   • 根据处理结果输出最小费用。

代码解释

• 邻接矩阵初始化：g数组初始化为INF，表示初始时交叉口之间无直接连接。
• 度数统计：degree数组记录每个交叉口的度数。
• 弗洛伊德算法：floyd函数计算所有交叉口之间的最短路径。
• 奇数度处理：找到两个奇数度交叉口，累加它们之间的最短路径到总费用。
• 结果输出：根据是否存在奇数度交叉口输出相应的最小费用。

该方法通过图论算法高效地解决了邮递员问题，确保在合理时间内计算出最小旅行费用。

代码

/* UVA117 POJ1237 The Postal Worker Rings Once */

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>

using namespace std;

/* Floyd-Warshall算法：计算图中任意2点之间的最短距离
 * 复杂度：O(N×N×N)
 * 输入：n 全局变量，图结点数
 *      g 全局变量，邻接矩阵，g[i][j]表示结点i到j间的边距离
 * 输出：g 全局变量
 */
const int INF = 0x3f3f3f3f;
const int N = 26;
int g[N][N];

void floyd()
{
    for(int k = 0; k < N; k++)
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

int degree[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    int ans = 0;
    memset(g, INF, sizeof(g));
    memset(degree, 0, sizeof(degree));
    while(cin >> s) {
        if(s == "deadend") {
            int u = -1, v = -1;
            for(int i = 0; i < N; i++)
                if(degree[i] & 1) {
                    if(u == -1) u = i;
                    else v = i;
                }

            floyd();

            if(u != -1) printf("%d\n", ans + g[u][v]);
            else printf("%d\n", ans);

            memset(g, INF, sizeof(g));
            memset(degree, 0, sizeof(degree));
            ans = 0;
        } else {
            g[s[s.size() - 1] - 'a'][s[0] - 'a'] = g[s[0] - 'a'][s[s.size() - 1] - 'a'] = s.size();
            degree[s[s.size() - 1] - 'a']++;
            degree[s[0] - 'a']++;
            ans += s.size();
        }
    }

    return 0;
}