poj 1679 The Unique MST (判断mst的唯一性,次小生成树)
题意:问最小生成树是否唯一。。
思路:求一下次小生成树。。。如果无解,或者次小生成树的权值之和和最小生成树的权值之和不同,那么唯一,否则不唯一。1A
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月12日 星期二 16时16分52秒
4File Name :code/poj/1679.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=105;
32int n,m;
33int ans;
34int f[N];
35struct Edge
36{
37 int u,v,w;
38 int in;
39 void input()
40 {
41 scanf("%d%d%d",&u,&v,&w);
42 }
43 bool operator < (Edge b)const
44 {
45 return w<b.w;
46 }
47}edge[N*N];
48void init()
49{
50 for ( int i = 1 ; i <= n ; i++) f[i] = i;
51}
52int root ( int x)
53{
54 if (x!=f[x]) f[x] = root(f[x]);
55 return f[x];
56}
57void merge( int x,int y)
58{
59 int rx = root(x);
60 int ry = root(y);
61 if (rx==ry) return ;
62 f[rx] = ry;
63}
64void kruskal( int k)
65{
66 for ( int i = 1 ; i <= n; i++) f[i] = i;
67 int cnt = 0 ;
68 int cur = 0 ;
69 for ( int i = 1; i <= m ; i++)
70 {
71 int u = edge[i].u;
72 int v = edge[i].v;
73 int w = edge[i].w;
74 if (i==k) continue;
75 if (root(u)==root(v)) continue;
76 merge(u,v);
77 cnt++;
78 cur+=w;
79 if (cnt>=n-1) break;
80 }
81 // cout<<"cnt:"<<cnt<<endl;
82 if (cnt<n-1) return ;
83 ans = min(ans,cur);
84}
85int main()
86{
87 #ifndef ONLINE_JUDGE
88 freopen("code/in.txt","r",stdin);
89 #endif
90 int T;
91 scanf("%d",&T);
92 while (T--)
93 {
94 scanf("%d%d",&n,&m);
95 init();
96 for ( int i = 1; i <= m ; i++) edge[i].input();
97 sort(edge+1,edge+m+1);
98 int cnt = 0 ;
99 int mst = 0 ;
100 for ( int i = 1 ; i <= m ; i++)
101 {
102 int u = edge[i].u;
103 int v = edge[i].v;
104 int w = edge[i].w;
105 if (root(u)==root(v)) continue;
106 edge[i].in = 1;
107 merge(u,v);
108 cnt++;
109 mst+=w;
110 }
111 ans = inf;
112 for ( int i = 1 ; i <= m ; i++)
113 {
114 if (edge[i].in==0) continue;
115 //cout<<"i:"<<i<<endl;
116 kruskal(i);
117 }
118 // cout<<"mst:"<<mst<<endl;
119 // cout<<"ans:"<<ans<<endl;
120 if (ans==inf)
121 {
122 printf("%d\n",mst);
123 }else
124 {
125 if (ans==mst) puts("Not Unique!");
126 else printf("%d\n",mst);
127 }
128 }
129 #ifndef ONLINE_JUDGE
130 fclose(stdin);
131 #endif
132 return 0;
133}