一、题意

有n个城市，m条道路，每条道路收费t元。
之后m行每行两个点表示一条道路。
要求你找到一条最短路径，使得该路径经过所有这m条道路。
输出路径的收费之和。

二、解析

别以为这是一道最短路或并查集问题，实际上这是一道欧拉回路问题。
那m条道路连接后，将会分成几个连通分量。每个连通分量需要统计其中奇数点的个数（通过一次dfs即可），然后先在这些连通分量内部加边来使之可以一笔画，然后再加边把所有连通分量连接起来。
需要注意的点：

  1. 连通分量可能只有一个点
  2. 有些城市可能压根就不参与，因此需要一个need[maxn]进行标记。
  3. m=0的情形

三、代码

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1000 + 5;
vector<int> G[maxn];
int n, m, t, kase = 1, vis[maxn], need[maxn];

int dfs(int u) {
    int res = G[u].size() % 2;
    vis[u] = 1;
    for(int v : G[u]) if(!vis[v]) {
        res += dfs(v);
    }
    return res;
}

int main() {
    while(cin >> n >> m >> t && n) {
        for(int i = 1; i <= n; i ++) G[i].clear();
        fill(need, need + n + 1, 0);
        for(int i = 0; i < m; i ++) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
            need[u] = need[v] = 1;
        }
        fill(vis, vis + n + 1, 0);
        int ans = m, block_num = 0;
        for(int i = 1; i <= n; i ++) if(need[i] && !vis[i]) {
            int res = dfs(i);
            ans += (res > 1 ? (res - 2) / 2 : 0);
            block_num ++;
        }
        ans += block_num - 1;
        if(m == 0) ans = 0;
        cout << "Case " << kase ++ << ": " << ans * t << endl;
    }
}

四、归纳

  • 欧拉回路：如果一个无向图是联通的，那么它最多只有两个奇点（一出一进）
  • 做题时多留心取值返回，比如这题m是可以等于0的