2006年第3题

题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=70

C语言源码：

#include<stdio.h>#include<stdlib.h>#define maxsize 10000typedef struct road{int a,b,len;}road;road r[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){road *aa=(road *)a;road *bb=(road *)b;return aa->len-bb->len;}int main(){int n,sum,i,roota,rootb;scanf("%d",&n);while(n){for(i=0;i<maxsize;i++)T[i]=-1;n=n*(n-1)/2;for(i=0;i<n;i++)scanf("%d %d %d",&r[i].a,&r[i].b,&r[i].len);qsort(r,n,sizeof(r[0]),cmp);sum=0;for(i=0;i<n;i++){roota=findroot(r[i].a);rootb=findroot(r[i].b);if(roota!=rootb){sum+=r[i].len;T[roota]=rootb;}}printf("%d\n",sum);scanf("%d",&n);}}