poj 1679 The Unique MST 判断最小生成树是否唯一（图论）

借用的是Kruskal的并查集，算法中的一点添加和改动。

通过判定其中有多少条可选的边，然后跟最小生成树所需边做比较，可选的边多于所选边，那么肯定方案不唯一。

如果不知道这个最小生成树的算法，还是先去理解下这个算法的原理，再继续看。

多加的几行与cnt2很类似的cnt1统计，是统计当前未选边中相同长度的边还有哪些可以选，但不标记，只是为了把当前可选的边全部统计出来。

其他细节，自己要细心点～

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <climits>
 8 #include <queue>
 9 
10 using namespace std;
11 
12 //Kruskal算法 求最小生成树是否唯一
13 
14 const int MAX = 110;
15 int F[MAX];
16 struct Edge
17 {
18     int u,v,w;
19 } edge[MAX*MAX];
20 int tol;
21 void addedge(int u,int v,int w)
22 {
23     edge[tol].u = u;
24     edge[tol].v = v;
25     edge[tol++].w = w;
26 }
27 bool cmp(Edge a,Edge b)
28 {
29     return a.w < b.w;
30 }
31 int find(int x)
32 {
33     if(F[x] == -1) return x;
34     else return F[x] = find(F[x]);
35 }
36 void Kruskal(int n)
37 {
38     memset(F,-1,sizeof(F));
39     sort(edge,edge+tol,cmp);
40     int cnt1 = 0,cnt2 =  0;
41     int ans = 0;
42     for(int i = 0; i < tol; )
43     {
44         int j = i;
45         while(j < tol && edge[j].w == edge[i].w)
46         {
47             int u = edge[j].u;
48             int v = edge[j].v;
49             int t1 = find(u);
50             int t2 = find(v);
51             if(t1 != t2)
52             {
53                 cnt1++;
54             }
55             j++;
56         }
57         j = i;
58         while(j < tol && edge[j].w == edge[i].w)
59         {
60             int u = edge[j].u;
61             int v = edge[j].v;
62             int w = edge[j].w;
63             int t1 = find(u);
64             int t2 = find(v);
65             if(t1 != t2)
66             {
67                 ans += w;
68                 F[t1] = t2;
69                 cnt2++;
70             }
71             j++;
72         }
73         i = j;
74         if(cnt2 == n - 1)
75             break;
76     }
77     //printf("%d %d
",cnt1,cnt2);
78     if(cnt1 > cnt2 || cnt2 != n -1)
79         printf("Not Unique!
");
80     else
81         printf("%d
",ans);
82 }
83 int main(void)
84 {
85     int t,m,n,i,x,y,w;
86     scanf("%d",&t);
87     while(t--)
88     {
89         scanf("%d %d",&n,&m);
90         tol = 0;
91         for(i = 0; i < m; i++)
92         {
93             scanf("%d %d %d",&x,&y,&w);
94             addedge(x,y,w);
95         }
96         Kruskal(n);
97     }
98     return 0;
99 }