poj1679 The Unique MST

思路：

使用Kruskal实现较为容易一些。

每次对权值相等（均为w）的边集E中的每条边e1, e2, e3 ... 逐一进行试探（但并不真正加入MST中），首先去掉E中那些与已经在MST中的边（这些边的权值是小于w的）冲突的边，如此得到E'。再将E'中的边逐一加入MST中，如果在加入的过程中发现E'中的边彼此之间有冲突，说明不唯一。

需要要在只剩一个连通分支的时候停止算法。（但是要将这一轮的边集E处理完，等到下一轮的时候再结束。）
实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct eg
 4 {
 5     int a, b, w;
 6 };
 7 eg es[23333];
 8 int fa[233];
 9 int find(int now)
10 {
11     if (fa[now] == now) return now;
12     return fa[now] = find(fa[now]);
13 }
14 bool uni0n(int a, int b)
15 {
16     a = find(a), b = find(b);
17     if (a != b) { fa[b] = a; return true; }
18     return false;
19 }
20 bool same(int a, int b)
21 {
22     return find(a) == find(b);
23 }
24 bool compare(const eg& x, const eg& y)
25 {
26     return x.w <= y.w;
27 }
28 int main()
29 {
30     int T, N, M;
31     scanf("%d", &T);
32     while (T--)
33     {
34         scanf("%d %d", &N, &M);
35         for (int i = 1; i <= N; i++) fa[i] = i;
36         for (int i = 1; i <= M; i++) scanf("%d %d %d", &es[i].a, &es[i].b, &es[i].w);
37         sort(es + 1, es + M + 1, compare);
38         int i = 1, cnt = N, sum = 0;
39         bool flg = true;
40         while (i <= M)
41         {            
42             if (!flg || cnt == 1) break;
43             vector<int> v;
44             int j = i;
45             while (j <= M && (j == i || es[j].w == es[j - 1].w))
46             {
47                 if (!same(es[j].a, es[j].b)) v.push_back(j);
48                 j++;
49             }
50             for (int k = 0; k < (int)v.size(); k++)
51             {
52                 if (!uni0n(es[v[k]].a, es[v[k]].b))
53                 {
54                     flg = false; break;
55                 }
56                 else 
57                 {
58                     cnt--; sum += es[v[k]].w;
59                 }
60             }
61             i = j;
62         }
63         if (flg) printf("%d
", sum);
64         else puts("Not Unique!");
65     } 
66     return 0;
67 }