本文共 1318 字，大约阅读时间需要 4 分钟。

继续畅通工程

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 5908    Accepted Submission(s): 2444

#include<stdio.h>

int father[104]; int n,i; typedef struct country{     int x;     int y;     int cost;     int build; }country; void init(){     for(i=1;i<=n;i++){         father[i]=i;     } } int compare(const void *a,const void *b){     return (*(country*)a).cost-(*(country*)b).cost; } int find(int x){     if(x==father[x]) return x;     find(father[x]); } int main(){     int cost,count,m,x,y;     country cou[5055];     while(scanf("%d",&n),n!=0){         cost=0,count=0;         init();         m=n*(n-1)/2;         for(i=0;i<m;i++){             scanf("%d%d%d%d",&cou[i].x,&cou[i].y,&cou[i].cost,&cou[i].build);             if(cou[i].build==1){                 cou[i].cost=0;             }         }         qsort(cou,m,sizeof(country),compare);         for(i=0;i<m;i++){             x=find(cou[i].x),y=find(cou[i].y);             if(x!=y){                 father[x]=y;                 cost+=cou[i].cost;                 count++;             }         }         printf("%d\n",cost);     }     return 0; }

转载地址：http://bxtpi.baihongyu.com/