題目描述：給定一個無向圖，要求判斷該圖的最小生成樹是否唯一，如果唯一的話輸出最小生成樹的權值，如果不唯一，輸出Not Unique！解題思路：要判斷最小生成樹是否唯一，可以求出次小生成樹，看權值是否和最小生成樹相等，如果相等的話說明最小生成樹不唯一，否則說明最小生成樹是唯一的，那么，只要求出次小生成樹來就好辦了。我用的是Kruskal算法求出最小生成樹來，然后依次枚舉這些樹邊并去掉，再求最小生成樹，所得的這些值的最小值就是次小生成樹的值，當然，前提是去掉一條樹邊以后，剩下的邊可以形成次小生成樹。ps：這題糊里糊涂就過了，不知道是不是數據太弱，我總感覺自己考慮不周全，卻不知道在哪里……
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,cas;
struct node
{
int u,v,w;
}edge[10000];
int sum,num;
int mst,smst=0x7fffffff;//mst----最小生成樹權值smst----次小生成樹權值
bool v[10000],can[10001];//v記錄是不是最小生成樹的樹邊，can記錄能否在求次小生成樹時用到某邊
int p[10001],rank[10001];
int Makeset()
{
int i;
for(i=1;i<=n;i++)
{
p[i]=i;
rank[i]=0;
}
return 0;
}
int Find(int t)
{
if(t!=p[t])
{
p[t]=Find(p[t]);
}
return p[t];
}
bool cmp(node a,node b)
{
return a.w<b.w;
}
int Union(int a,int b)
{
int x=Find(a);
int y=Find(b);
if(rank[x]>rank[y])
{
p[y]=x;
}
else
{
p[x]=y;
if(rank[x]==rank[y])
{
rank[y]++;
}
}
return 0;
}
int Kruskal()
{
num=0;
sum=0;
Makeset();
int i;
for(i=0;i<m;i++)
{
if(Find(edge[i].u)!=Find(edge[i].v))
{
Union(edge[i].u,edge[i].v);
sum+=edge[i].w;
v[i]=1;
num++;
}
if(num==n-1)
break;
}
return sum;
}
int Sec_Kruskal()
{
num=0;
sum=0;
int i;
Makeset();
for(i=0;i<m;i++)
{
if(can[i])
{
if(Find(edge[i].u)!=Find(edge[i].v))
{
Union(edge[i].u,edge[i].v);
sum+=edge[i].w;
num++;
}
if(num==n-1)
break;
}
}
return sum;
}
int main()
{
int i,j;
scanf("%d",&cas);
while(cas--)
{
smst=0x7fffffff;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
memset(can,1,sizeof(can));
memset(v,0,sizeof(v));
sort(edge,edge+m,cmp);
mst=Kruskal();
for(i=0;i<m;i++)
{
if(v[i])
{
can[i]=0;
int tmp=Sec_Kruskal();
if(tmp>=mst&&smst>tmp)//如果tmp<mst說明不能形成次小生成樹
{
smst=tmp;
}
can[i]=1;
}
}
if(mst==smst&&smst!=0)
{
printf("Not Unique!\n");
}
else
{
printf("%d\n",mst);
}
//printf("%d %d\n",mst,smst);
}
//system("pause");
return 0;
}