POJ 1679 The Unique MST（求最小生成树是否唯一）

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <string>
 5 #include <iomanip>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <vector>
 9 #include <map>
10 using namespace std;
11 struct Node{
12     int u, v, w;
13 }node[110*110/2];
14 int t, n, m, sum1, sum2,  ans1, ans2;
15 int pre[110], mark[110*110/2];
16 int find(int x){
17     if(pre[x] == x) return x;
18     else return find(pre[x]);
19 }
20 bool cmp(Node x, Node y){
21     return x.w < y.w;
22 }
23 
24 int main(){
25     scanf("%d", &t);
26     while(t--){
27         scanf("%d%d", &n, &m);
28         for(int i = 1; i <= m; i++){
29             scanf("%d%d%d", &node[i].u, &node[i].v, &node[i].w);
30         }
31         sort(node+1,node+1+m,cmp);
32         sum1 = 0;
33         ans1 = 0;
34         for(int i = 1; i <= n; i++) pre[i] = i;
35         for(int i = 1; i <= m; i++){
36             if(ans1 == n-1) break;
37             int aa = find(node[i].u);
38             int bb = find(node[i].v);
39             if(aa != bb){
40                 sum1 += node[i].w;
41                 pre[aa] = bb;
42                 mark[++ans1] = i;
43             //    ans++;
44             }
45         }
46         bool flag = true;
47         for(int k = 1; k <= ans1; k++){
48             for(int i = 1; i <= n; i++) pre[i] = i;
49             sum2 = 0; ans2 = 0;
50             for(int i = 1; i <= m; i++){
51                 if(i == mark[k]) continue;
52                 if(ans2 == n-1) break;
53                 int aa = find(node[i].u);
54                 int bb = find(node[i].v);
55                 if(aa != bb){
56                     sum2 += node[i].w;
57                     pre[aa] = bb;
58                     ans2++;
59                 }
60             }
61             if(ans2 == n-1 && sum2 == sum1){
62                 flag = false; break;
63             }
64         }
65         if(flag) printf("%d\n", sum1);
66         else printf("Not Unique!\n");
67         
68         
69 
70     }
71     
72     return 0;
73 }