POJ 1679 判最小生成树的不唯一性

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 105
 6 int fa[N] , same[N] , first[N] , k;
 7 int rec[N] , amo;//rec[]记录MST中含有相同长度边的位置,amo记录其数量
 8 struct Edge{
 9     int x,y,d,next,flag;
10     bool same;
11     bool operator<(const Edge &m) const{
12         return d<m.d;
13     }
14 }e[N*N];
15 
16 int find_head(int x)
17 {
18     while(fa[x]!=x) x=fa[x];
19     return x;
20 }
21 
22 bool Union(int x,int y)
23 {
24     int fa_x = find_head(x);
25     int fa_y = find_head(y);
26     fa[fa_x] = fa_y;
27     return fa_x == fa_y;
28 }
29 
30 void add_edge(int x, int y , int d)
31 {
32     e[k].x=x , e[k].y=y , e[k].d=d , e[k].flag=1 , e[k].next=first[x];
33     e[k].same = false;
34     first[x] = k++;
35 }
36 
37 int cal_MST(int n , int flag)
38 {
39     int ans = 0 , cnt=0;
40     for(int i=1 ; i<=n ; i++) fa[i]=i;
41     for(int i=0 ; i<k ; i++){
42         if(e[i].flag==1){
43             if(!Union(e[i].x , e[i].y)){
44                 ans+=e[i].d;
45                 if(e[i].same && flag){
46                     rec[amo++] = i;
47                 }
48                 cnt++;
49                 if(cnt == n-1) break;
50             }
51         }
52     }
53     return ans;
54 }
55 
56 int main()
57 {
58     int T;
59     scanf("%d" , &T);
60     while(T--)
61     {
62         int n , m , x , y , d;
63         scanf("%d%d" , &n , &m);
64         k=0;
65         memset(first , -1 , sizeof(first));
66         for(int i=0 ; i<m ; i++){
67             scanf("%d%d%d" , &x , &y , &d);
68             add_edge(x , y , d);
69         }
70 
71         sort(e , e+k);
72         //对存在相同边的边进行标记
73         for(int i=1 ; i<k ; i++)
74             if(e[i].d == e[i-1].d) e[i].same=e[i-1].same=true;
75         amo = 0;
76         int ans = cal_MST(n , 1);
77         bool is_unique = true;
78         for(int i=0 ; i<amo ; i++){
79             e[rec[i]].flag = 0;
80             int t=cal_MST(n , 0);
81             if(t == ans){
82                 is_unique=false;
83                 break;
84             }
85             e[rec[i]].flag = 1;
86         }
87         if(is_unique) printf("%d\n" , ans);
88         else puts("Not Unique!");
89     }
90     return 0;
91 }