poj 1679（次小生成树）

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-02-10 15:50
 5  * Filename     : poj_1679.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 101;
34 int Map[LEN][LEN];
35 int n, m, top, fa[LEN], dis[LEN][LEN], tag[LEN*LEN], vis[LEN];
36 struct E{
37     int u, v, val;
38 }edge[LEN*LEN];
39 
40 bool cmp(E a, E b){return a.val < b.val;}
41 void init(){for(int i=0; i<LEN; i++) fa[i] = i;}
42 int Find(int x){return fa[x] == x ? x : fa[x] = Find(fa[x]);}
43 
44 int kruskal(){
45     int cnt = 0, ret = 0;
46     init();
47     memset(tag, 0, sizeof tag);
48     sort(edge, edge+m, cmp);
49     for(int i=0; i<m; i++){
50         int pa = Find(edge[i].u), pb = Find(edge[i].v);
51         if(pa == pb) continue;
52         fa[pa] = pb;
53         cnt ++;
54         Map[edge[i].u][edge[i].v] = Map[edge[i].v][edge[i].u] = edge[i].val;
55         tag[i] = 1;
56         ret += edge[i].val;
57         if(cnt == n-1) break;
58     }
59     return ret;
60 }
61 
62 void dfs(int bg, int v, int val){
63     vis[v] = 1;
64     dis[bg][v] = val;
65     for(int i=1; i<=n; i++){
66         if(Map[v][i] != INF && vis[i] == 0) dfs(bg, i, max(val, Map[v][i]));
67     }
68 }
69 
70 int main()
71 {
72 //    freopen("in.txt", "r", stdin);
73 
74     int T;
75     scanf("%d", &T);
76     while(T--){
77         memset(Map, 0x3f, sizeof Map);
78         memset(dis, 0, sizeof dis);
79         scanf("%d%d", &n, &m);
80         for(int i=0; i<m; i++){
81             scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].val);
82         }
83         int ans = kruskal();
84         for(int i=1; i<=n; i++){
85             memset(vis, 0, sizeof vis);
86             dfs(i, i, 0);
87         }
88         int f = 1;
89         for(int i=0; i<m; i++){
90             if(tag[i])continue;
91             if(edge[i].val == dis[edge[i].u][edge[i].v]) f = 0;
92         }
93         if(f)printf("%d\n", ans);
94         else printf("Not Unique!\n");
95     }
96     return 0;
97 }