九度教程第75题

C语言源码：
[cpp]  
#include<stdio.h>  
#include<stdlib.h>  
#define maxsize 100  
typedef struct edge  
{  
    int a,b;  
    int weight;  
}edge;  
edge finished[maxsize*maxsize/2],notfinished[maxsize*maxsize/2];  
int T[maxsize];  
int findroot(int x)  
{  
    int temp;  
    if(T[x]==-1)  
        return x;  
    else  
    {  
        temp=findroot(T[x]);  
        T[x]=temp;  
        return temp;  
    }  
}  
int cmp(const void *a,const void *b)  
{  
    edge *aa=(edge *)a;  
    edge *bb=(edge *)b;  
    return aa->weight-bb->weight;  
}  
int main()  
{  
    int n,a,b,c,d,topf,topn,min,i,roota,rootb;  
    scanf("%d",&n);  
    while(n)  
    {  
        topf=0;  
        topn=0;  
        for(i=1;i<=n*(n-1)/2;i++)  
        {  
            scanf("%d %d %d %d",&a,&b,&c,&d);  
            if(d==0)  
            {  
                notfinished[topn].a=a-1;  
                notfinished[topn].b=b-1;  
                notfinished[topn++].weight=c;  
            }  
            else  
            {  
                finished[topf].a=a-1;  
                finished[topf].b=b-1;  
                finished[topf++].weight=c;  
            }  
        }  
        for(i=0;i<n;i++)  
            T[i]=-1;  
        for(i=0;i<topf;i++)  
        {  
            roota=findroot(finished[i].a);  
            rootb=findroot(finished[i].b);  
            if(roota!=rootb)  
                T[rootb]=roota;  
        }  
        min=0;   www.zzzyk.com
        qsort(notfinished,topn,sizeof(notfinished[0]),cmp);  
        for(i=0;i<topn;i++)  
        {  
            roota=findroot(notfinished[i].a);  
            rootb=findroot(notfinished[i].b);  
            if(roota!=rootb)  
            {  
                T[rootb]=roota;  
                min+=notfinished[i].weight;  
            }  
        }  
        printf("%d\n",min);  
        scanf("%d",&n);  
    }  
}  

补充：软件开发 , C++ ,

上一个：九度教程第76题
下一个：九度教程第74题