Uva12118-Inspetor's Dilemma-DFS求连通+欧拉路

发表于 | 分类于 ， | | 阅读次数:

V个城市之间两两相连，给定E条需要走的边，走过一条边需要时间T。求走完所有的E条边需要的最少时间。E条边不一定在一个连通图中。
竟然卡在ifndef ONLINE_JUDGE上好久，单词ONLINE手滑打成了ONLIEN，= =。吐血。

紫书第六章结束

链接

题目链接Uva12118-Inspetor’s Dilemma
参考SingleK’s Blog精简了自己的代码。

题解

因为E条边不一定在一个连通图中，所以首先DFS遍历连通块，统计每一个连通块中度数为奇数的结点个数。若能满足构成欧拉路的条件，则一次“一笔画”就可以走完当前连通块中的边。若不能构成欧拉路（奇度数结点个数大于2），则通过加边的方式，使其可以构成欧拉路。n个连通块之间还需要n - 1条边连接。
所以最后的所需要走过的边是E，加上添加边的个数，再加上连通块个数减1。

最后不要忘记乘以T得到总耗时 = =，以及当给定E为0时，结果会出现负数，要特判。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
 *
 * Author : Aincrad
 *
 * Date : Sat 15 Dec 17:21:07 CST 2018
 *
 */

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 7;
int V, E, T;
bool vis[maxn];
vector<int> d[maxn];
int ans;
int odd;

void dfs(int u){
    vis[u] = 1;
    if(d[u].size() % 2) odd++;
    for(size_t i = 0; i < d[u].size(); i++){
        int v = d[u][i];
        if(!vis[v]){
            dfs(v);
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif

    int kase = 0;
    while(cin >> V >> E >> T){
        if(V == 0 && E == 0 && T == 0) break;
        kase++;
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= V; i++){
            d[i].clear();
        }
        ans = 0;

        int u, v;
        for(int i = 0; i < E; i++){
            cin >> u >> v;
            d[u].push_back(v);
            d[v].push_back(u);
        }

        int cnt = 0;
        for(int i = 1; i <= V; i++){
            odd = 0;
            if(!d[i].empty() && !vis[i]){
                dfs(i);
                cnt++;
                if(odd > 2) ans += (odd - 2) / 2;
            }
        }
        ans += E;
        ans += cnt - 1;
        ans *= T;
        if(ans < 0) cout << "Case " << kase << ": " << 0 << endl;
        else cout << "Case " << kase << ": " << ans << endl;
    }
    return 0;
}