poj 1679 The Unique MST (判断mst的唯一性，次小生成树)
poj1679
题意：问最小生成树是否唯一。。
思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。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}