題意：判斷最小生成樹是否唯一
思路：第一次用kruskal求出最小生成樹，記為ans,然後依次去除已經選進來的邊，進行kruskal，如果ans==kruskal()的話，則輸出不唯一。
注意：1.第一次求kruskal時記得要先判斷是否能生成最小生成樹（但是我沒判斷就A了。。理論上來說是要判斷的。。）
2.注意存放變的數組開大一點。我用G++交了幾次一直WA，原代碼改成C++交就RE，然後數組改了下大小就A了。被G++坑死了。
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 20005
#define inf 1<<28
using namespace std;
struct kdq
{
int s,e,l;
} road[Max];
int f[Max];
bool visit[Max];
bool visit1[Max];
int n,m;
bool cmp(kdq x,kdq y )
{
return x.l<y.l;
}
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
void Union(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)return ;
if(y>x)
f[y]=x;
else
f[x]=y;
}
int kruskal(int d)//d是用來刪除邊的
{
int num=0;
int num1=0;
for(int i=0; i<m; i++)
{
if(i!=d)
{
int x=find(road[i].s);
int y=find(road[i].e);
if(y!=x)
{
num1++;
Union(x,y);
num+=road[i].l;
visit[i]=1;//記錄第一次取來的邊的標號
}
}
}
if(num1==n-1)//判斷能生成最小生成樹
return num;
else
return -1;
}
int main()
{
int i,j,k,l,T;
cin>>T;
while(T--)
{
memset(visit,0,sizeof(visit));
cin>>n>>m;
for(i=0; i<=n; i++)
f[i]=i;
for(i=0; i<m; i++)
scanf("%d%d%d",&road[i].s,&road[i].e,&road[i].l);
sort(road,road+m,cmp);
int ans=kruskal(-1);
for(i=0; i<m; i++)
visit1[i]=visit[i];//將第一標記的序號存入visit1[],因為visit[]在接下來的kruskal中還會改變
if(ans==-1)//這個判斷不需要也可以過。。難道是數據水了？
{
cout<<0<<endl;
continue;
}
bool flag=0;
for(i=0; i<m; i++)
{
if(visit1[i])//如果是第一次取到的邊
{
for(j=0; j<=n; j++)
f[j]=j;
if(kruskal(i)==ans)//如果刪除了這條邊後，最小生成樹的值相等，則說明不唯一
{
flag=1;
break;
}
}
}
if(flag)
cout<<"Not Unique!"<<endl;
else
cout<<ans<<endl;
}
return 0;
}
作者：kdqzzxxcc
