1
http://poj.org/problem?id=1679
参考 ：
http://hi.baidu.com/buaa_babt/blog/item/55a7dca78246e49e4610647e.html
/*
2 求次小生成树，用kruskal算法 ，第一次求出最小生成树，并将选过的边标记
3 然后 枚举删除选过的边，求删除此边后的最小生成树
4 */
5
6 #include<stdio.h>
7 #define maxn 10000
8 #include<algorithm>
9 #define inf 0xffffff
10 #include<string.h>
11 using namespace std;
12 struct node
13 {
14 int x;
15 int y;
16 int w;
17 int vis;
18
19 }p[maxn*100];
20 int sum,n,m;
21 int f[maxn],vis[maxn*100];
22 int cmp1(const node a,const node b)
23 {
24 return a.w<b.w;
25 }
26 int find(int x)
27 {
28 if(f[x]!=x)f[x]=find(f[x]);
29 return f[x];
30 }
31 int MST()
32 {
33 int i,num=0;
34 for(i=0;i<=n;i++)f[i]=i;
35 for(i=0;i<m;i++)
36 {
37 int x=p[i].x;
38 int y=p[i].y;
39 int a=find(x);
40 int b=find(y);
41 if(a!=b)
42 {
43 f[a]=b;
44 sum+=p[i].w;
45
46 num++;
47 p[i].vis=1;
48 }
49 }
50 if(num<n-1)return 0;
51 else return 1;
52
53 }
54 int SMST()
55 {
56 int ans=0,num=0,i;
57 for(i=0;i<=n;i++)f[i]=i;
58 for(i=0;i<m;i++)
59 {
60 if(!vis[i])
61 {
62 int a=find(p[i].x);
63 int b=find(p[i].y);
64 if(a!=b)
65 {
66 f[a]=b;
67 ans+=p[i].w;
68 num++;
69
70 }
71 }
72 }
73 if(num<n-1) return inf;
74 else return ans;
75 }
76 int main()
77 {
78 int T;
79 int i;
80 scanf("%d",&T);
81 while(T--)
82 {
83 scanf("%d%d",&n,&m);
84
85 for(i=0;i<m;i++)
86 {
87 scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
88 p[i].vis=0;
89 }
90 sort(p,p+m,cmp1);
91
92
93 sum=0;
94 int k= MST();
95
96 int ans=inf;
97 for(i=0;i<m;i++)
98 {
99 if(p[i].vis)
100 {
101
102 vis[i]=1;
103 ans=min(ans,SMST());
104 vis[i]=0;
105 }
106
107 }
108 if(ans!=sum)printf("%d\n",sum);
109 else printf("Not Unique!\n");
110
111
112 }
113
114 }