poj 1679 The Unique MST (判断mst的唯一性，次小生成树)

  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}