九度教程第74题

C语言源码：
[cpp]  
#include<stdio.h>  
#include<stdlib.h>  
#define maxsize 110  
typedef struct edge  
{  
    int a,b;  
    int weight;  
}edge;  
edge E[maxsize];  
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,m,weight,i,num,roota,rootb;  
    scanf("%d %d",&n,&m);  
    while(n)  
    {  
        for(i=0;i<n;i++)  
            scanf("%d %d %d",&E[i].a,&E[i].b,&E[i].weight);  
        qsort(E,n,sizeof(E[0]),cmp);  
        for(i=1;i<=m;i++)  
            T[i]=-1;  
        weight=0;  
        num=0;  
        for(i=0;i<n;i++)  
        {  
            roota=findroot(E[i].a);  
            rootb=findroot(E[i].b);  
            if(roota!=rootb)  
            {  
                T[rootb]=roota;  
                weight+=E[i].weight;  
            }  
        }  
        for(i=1;i<=m;i++)  
            if(T[i]==-1)  
                num++;  
        if(num>1)  
            printf("?\n");  
        else  
            printf("%d\n",weight);  
        scanf("%d %d",&n,&m);  
    }  
}  
 

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

上一个：九度教程第75题
下一个：九度教程第73题