poj1679(The Unique MST)Kruskal
最近略忙，就不写题意思路什么的，直接上代码。
#include<stdio.h>
#include<stdlib.h>
struct edge
{
int u,v,w,flag;
}p[4952];
int n,m;
int f[101];
int used[101];
int cmp(const void*aa,const void*bb)
{
return ((struct edge*)aa)->w-((struct edge*)bb)->w;
}
int find(int x)
{
return f[x]==x?x:(f[x]=find(f[x]));
}
int Kruskal()
{
int sum=0,i,x,y,t=0;
for(i=0;i<m;i++)
{
x=find(p[i].u);
y=find(p[i].v);
if(x!=y)
{
f[x]=y;
sum+=p[i].w;
used[t]=i;
t++;
if(t==n-1) break;
}
}
return sum;
}
int reKruskal()
{
int sum=0,i,x,y,t=0;
for(i=0;i<m;i++)
{
x=find(p[i].u);
y=find(p[i].v);
if(x!=y&&!p[i].flag)
{
f[x]=y;
sum+=p[i].w;
t++;
if(t==n-1) break;
}
}
return sum;
}
int main()
{
//freopen("12.3.4.input.txt","r",stdin);
int t,i,j,ans,tans,k,pt=0;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d %d",&n,&m);
for(j=1;j<=n;j++) f[j]=j;
for(j=0;j<n;j++) used[j]=-1;
for(j=0;j<m;j++)
{
scanf("%d %d %d",&p[j].u,&p[j].v,&p[j].w);
p[j].flag=0;
}
qsort(p,m,sizeof(p[0]),cmp);
ans=Kruskal();
pt=0;
for(j=0;j<n-1;j++)
{
p[used[j]].flag=1;
for(k=1;k<=n;k++) f[k]=k;
tans=reKruskal();
p[used[j]].flag=0;
if(ans==tans&&ans!=0)
{
pt=1;
break;
}
}
if(pt) printf("Not Unique!\n");
else printf("%d\n",ans);
}
return 0;
}