题目描述：给定一个无向图，要求判断该图的最小生成树是否唯一，如果唯一的话输出最小生成树的权值，如果不唯一，输出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;
}