题目：http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2144&cid=1186
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 int bin[110]; 5 struct node 6 { 7 int u,v,w; 8 }q[10001]; 9 10 int cmp(const void *a,const void *b)//按距离从小到大排序 11 { 12 return (*(node *)a).w-(*(node *)b).w; 13 } 14 int find(int a) 15 { 16 if(a==bin[a]) 17 return a; 18 else 19 bin[a]=find(bin[a]); 20 }; 21 int main() 22 { 23 int n,m,i,j,sum,num; 24 int x,y; 25 while(~scanf("%d%d",&n,&m)) 26 { 27 sum=0; num=0; 28 for(i=1; i<=n; i++) 29 bin[i]=i; 30 for(i=0; i<=m-1; i++) 31 scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w); 32 qsort(q,m,sizeof(q[0]),cmp); 33 for(i=0; i<=m-1; i++) 34 { 35 x=find(q[i].u); y=find(q[i].v); 36 if(x!=y) //检查是否连通 37 { 38 sum+=q[i].w;//没连通的话加上距离 39 num++; //城市+1 40 bin[x]=y; 41 } 42 if(num==n-1) 43 break; 44 } 45 printf("%d ",sum); 46 } 47 }