题目地址：http://ac.jobdu.com/problem.php?cid=1040&pid=74
免费地址：http://acmclub.com/problem.php?id=1145
//九度OJ教程75 kruskal求最小生成树之《继续畅通工程》//http://ac.jobdu.com/problem.php?cid=1040&pid=74//Tip:先用qsort排序，然后顺序遍历直到完成。#include <stdio.h>#include <stdlib.h>#define N 10000typedef struct E{ int a,b; int value; int over;}E;int cmp(const void *a,const void *b){ E *aa=(E *)a,*bb=(E *)b; return aa->value-bb->value;}int Tree[N]={0};int findroot(int a){ if(!Tree[a])return a; int temp=findroot(Tree[a]); Tree[a]=temp; return temp;}int main(){ int i,j,m,n,a,b,sum; E ss[N]; while(~scanf("%d",&n)&&n) { m=n*(n-1)/2; for(i=0;i<N;i++)Tree[i]=0; for(i=0;i<m;i++) { scanf("%d %d %d %d",&ss[i].a,&ss[i].b,&ss[i].value,&ss[i].over); if(ss[i].over) { int tempa=findroot(ss[i].a); int tempb=findroot(ss[i].b); if(tempa^tempb)Tree[tempa]=tempb; i--; m--; } } qsort(ss,m,sizeof(ss[0]),cmp); for(i=sum=0;i<m;i++) { a=findroot(ss[i].a); b=findroot(ss[i].b); if(a^b) { Tree[a]=b; sum+=ss[i].value; } } printf("%d\n",sum); } return 0;}