2007年第5题

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

C语言源码：

#include<stdio.h>#include<stdlib.h>typedef struct road{int a,b,len;}road;road r[101];int T[101];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 i,n,m,num,len,roota,rootb;scanf("%d %d",&n,&m);while(n){for(i=0;i<n;i++)scanf("%d %d %d",&r[i].a,&r[i].b,&r[i].len);for(i=0;i<101;i++)T[i]=-1;qsort(r,n,sizeof(r[i]),cmp);num=0;len=0;for(i=0;i<n;i++){roota=findroot(r[i].a);rootb=findroot(r[i].b);if(roota!=rootb){num++;len+=r[i].len;T[roota]=rootb;}}if(num==m-1)printf("%d\n",len);elseprintf("?\n");scanf("%d %d",&n,&m);}}