UVA-10462.Is There A Second Way Left(Kruskal+次小生成树)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 5, maxe = 200 + 5, INF = 0x3f3f3f3f;
 8 int n, m, pir[maxn], Max[maxn][maxn];
 9 vector <int> G[maxn];
10 struct Edge {
11     int u, v, w;
12     bool vis;
13 }edge[maxe];
14 
15 int Find(int x) {
16     if(x == pir[x]) return x;
17     return pir[x] = Find(pir[x]);
18 }
19 
20 bool cmp(const Edge &a, const Edge &b) {
21     return a.w < b.w;
22 }
23 
24 int Kruskal() {
25     sort(edge + 1, edge + m + 1, cmp);
26     int ans = 0, cnt = 0;
27     for(int i = 1; i <= n; i ++) {
28         G[i].clear();
29         G[i].push_back(i);
30         pir[i] = i;
31     }
32     for(int i = 1; i <= m; i ++) {
33         int fx = Find(edge[i].u), fy = Find(edge[i].v);
34         if(cnt == n - 1) break;
35         if(fx != fy) {
36             cnt ++;
37             edge[i].vis = true;
38             ans += edge[i].w;
39             int len_fx = G[fx].size(), len_fy = G[fy].size();
40             for(int j = 0; j < len_fx; j ++) {
41                 for(int k = 0; k < len_fy; k ++) {
42                     Max[G[fx][j]][G[fy][k]] = Max[G[fy][k]][G[fx][j]] = edge[i].w;
43                 }
44             }
45             pir[fx] = fy;
46             for(int j = 0; j < len_fx; j ++)
47                 G[fy].push_back(G[fx][j]);
48         }
49     }
50     if(cnt < n - 1) return INF;
51     return ans;
52 }
53 
54 int Second_Kruskal(int MST) {
55     int ans = INF;
56     for(int i = 1; i <= m; i ++) {
57         if(!edge[i].vis)
58             ans = min(ans, MST + edge[i].w - Max[edge[i].u][edge[i].v]);
59     }
60     return ans;
61 }
62 
63 int main () {
64     int t, Case = 0;
65     scanf("%d", &t);
66     while(t --) {
67         scanf("%d %d", &n, &m);
68         for(int i = 1; i <= m; i ++) {
69             scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
70             edge[i].vis = false;
71         }
72         printf("Case #%d : ", ++Case);
73         int MST = Kruskal();
74         if(MST == INF) {
75             printf("No way\n");
76             continue;
77         }
78         int Second_MST = Second_Kruskal(MST);
79         if(Second_MST == INF) printf("No second way\n");
80         else printf("%d\n", Second_MST);
81     }
82     return 0;
83 }