Question

HDOJ 1879不知道自己哪里错了，希望大神们出头帮忙，题目http://acm.hdu.edu.cn/showproblem.php?pid=1879

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int n,m,i,x,y,k,sum,a[5000],b[5000];
struct ac
{
int x,y,z,q;
}ca[5000];
int f (int x)
{
if(a[x]!=x)
a[x]=f(x);
return a[x];
}
void un (int x,int y)
{
x=f(x);
y=f(y);
if(x==y)
return ;
if(b[x]>b[y])
b[y]=x;
else
{
if(b[x]==b[y])
b[y]++;
b[x]=y;
}
}
int p (const void *a,const void *b)
{
return (*(ac*)a).z-(*(ac*)b).z;
}
int main()
{
while(scanf("%d",&n)!=EOF,n)
{
k=0;
sum=0;
m=n*(n-1)/2;
for(i=1;i<=n;i++)
{
a[i]=i;
b[i]=0;
}
for(i=1;i<=m;i++)
scanf("%d%d%d%d",&ca[i].x,&ca[i].y,&ca[i].z,&ca[i].q);
qsort(ca+1,m,sizeof(ac),p);
for(i=1;i<=m;i++)
{
if(ca[i].q==1)
{
un(ca[i].x,ca[i].y);
k++;
if(k==n-1)
break;
}
}
if(k!=n-1)
{
for(i=1;i<=m;i++)
{
x=f(ca[i].x);
y=f(ca[i].y);
if(x!=y)
{
un(ca[i].x,ca[i].y);
k++;
sum=sum+ca[i].z;
if(k==n-1)
break;
}
}
}
printf("%d\n",sum);
}
return 0;
}

Answer 1

此题采用最小生成树思想：并查集