次小生成树

佚名 5年前 (2019-04-09) 随笔 1060人围观抢沙发百度已收录

POJ – 1679 – The Unique MST（次小生成树）

我写了个暴力的算法，先求一遍最小生成树。然后枚举所有最小生成树的边依次删除，每次再计算一次最小生成树，取最小值，然后和一开始求的值比较。原理是次小生成树的边一定至少有一条和最小生成树的不一样。
注意：删除一条边之后图可能不连通，不连通的图没有生成树，应该返回最大值。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define maxn 10005
 5 struct edge{
 6     int u, v, c, p;
 7 }g[maxn];
 8 int par[maxn], n, m;
 9 int find(int x){return par[x] < 0 ? x : par[x] = find(par[x]);}
10 bool comp(const edge &a, const edge &b){return a.c < b.c;}
11 int mst()
12 {
13     memset(par, -1, sizeof(par));
14     int ans = 0;
15     for (int i = 0; i < m; ++i){
16         if (g[i].p == 2) continue;
17         int x = find(g[i].u), y = find(g[i].v);
18         if (x != y){
19             ans += g[i].c;
20             par[x] += par[y];
21             par[y] = x;
22         }
23     }
24     if (-par[find(g[0].u)] != n) return 0x3f3f3f3f;
25     else return ans;
26 }
27 int main()
28 {
29     int t;
30     scanf("%d", &t);
31     while (t--){
32         scanf("%d %d", &n, &m);
33         for (int i = 0; i < m; ++i) scanf("%d %d %d", &g[i].u, &g[i].v, &g[i].c);
34         std::sort(g, g + m, comp);
35         int ans = 0;
36         memset(par, -1, sizeof(par));
37         for (int i = 0; i < m; ++i){
38             int x = find(g[i].u), y = find(g[i].v);
39             if (x != y){
40                 g[i].p = 1;
41                 ans += g[i].c;
42                 par[x] += par[y];
43                 par[y] = x;
44             }
45         }
46         if (-par[find(g[0].u)] != n) puts("Not Unique!");
47         else{
48             int tans = 0x3f3f3f3f;
49             for (int i = 0; i < m; ++i){
50                 if (g[i].p == 1){
51                     g[i].p = 2;
52                     tans = std::min(tans, mst());
53                     g[i].p = 0;
54                 }
55             }
56             if (ans == tans) puts("Not Unique!");
57             else printf("%d\n", ans);
58         }
59     }
60     return 0;
61 }