hdu 1879 继续畅通工程 （并查集）

#include<stdio.h>
#include<string.h>
int map[105][105],vis[105][105],ans,n,father[105];
int find(int x)
{
    while(x!=father[x])
        x=father[x];
    return x;
}
int main()
{
    int i,j,k,a,b,d,t,min1,min2,state,tt,num;
    while(scanf("%d",&n)==1 && n)
    {
        memset(vis,0,sizeof(vis));
        memset(map,0,sizeof(map));
        t=n*(n-1)/2;num=n;ans=0;
        for(i=1;i<=n;i++)
            father[i]=i;
        for(i=0;i<t;i++)
        {
            scanf("%d%d%d%d",&a,&b,&d,&state);
            if(a<b) map[a][b]=d;
            else map[b][a]=d;
            if(state) 
            {
                if(a<b) vis[a][b]=1;
                else vis[b][a]=1;
                a=find(a);b=find(b);
                if(a!=b)
                {
                    if(a>b) father[a]=b;
                    else father[b]=a;
                    num--;
                }
            }
        }
        if(num==1)
        {
            printf("0\n");continue;
        }
        for(k=1;k<n;k++)
        {
            tt=1;
            for(i=1;i<n;i++)
            {
                for(j=i+1;j<=n;j++)
                {
                    a=find(i);b=find(j);
                    if(vis[i][j]==0 && a!=b)
                    {
                        if(tt)
                        {
                            min1=i;min2=j;tt=0;
                        }
                        else if(map[min1][min2]>map[i][j])
                        {
                            min1=i;min2=j;
                        }
                    }
                }
            }
            ans+=map[min1][min2];num--;vis[min1][min2]=1;
            min1=find(min1);min2=find(min2);
            if(min1>min2) father[min1]=min2;
            else father[min2]=min1;
            if(num==1) break;
        }
        printf("%d\n",ans);
    }
    return 0;
}