九度教程第73题

C语言源码：
[cpp] 
#include<stdio.h>  
#include<stdlib.h>  
#define maxsize 1000  
typedef struct edge  
{  
    int a,b;  
    int weight;  
}edge;  
edge E[maxsize];  
int T[27];  
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)  
{  
    struct edge *aa=(edge *)a;  
    struct edge *bb=(edge *)b;  
    return aa->weight-bb->weight;  
}  
int main()  
{  
    int n,weight,k,i,j,top,roota,rootb,min;  
    char point1,point2;  
    scanf("%d",&n);  
    getchar();  
    while(n)  
    {  
        top=0;  
        for(i=0;i<n-1;i++)  
        {  
            point1=getchar();  
            scanf("%d",&k);  
            getchar();  
            while(k--)  
            {  
                point2=getchar();  
                getchar();  
                scanf("%d",&weight);  
                getchar();  
                E[top].a=point1-'A';  
                E[top].b=point2-'A';  
                E[top++].weight=weight;  
            }  
  
        }  
        qsort(E,top,sizeof(E[0]),cmp);  
        for(i=0;i<n;i++)  
            T[i]=-1;  
        min=0;  
        for(i=0;i<top;i++)  
        {  www.zzzyk.com
            roota=findroot(E[i].a);  
            rootb=findroot(E[i].b);  
            if(roota!=rootb)  
            {  
                T[rootb]=roota;  
                min+=E[i].weight;  
            }  
        }  
        printf("%d\n",min);  
        scanf("%d",&n);  
        getchar();  
    }  
}  
 

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

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