C語言源碼： [cpp] #include<stdio.h> #include<stdlib.h> #define maxsize 100 typedef struct edge { int a,b; int weight; }edge; edge finished[maxsize*maxsize/2],notfinished[maxsize*maxsize/2]; 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) { edge *aa=(edge *)a; edge *bb=(edge *)b; return aa->weight-bb->weight; } int main() { int n,a,b,c,d,topf,topn,min,i,roota,rootb; scanf("%d",&n); while(n) { topf=0; topn=0; for(i=1;i<=n*(n-1)/2;i++) { scanf("%d %d %d %d",&a,&b,&c,&d); if(d==0) { notfinished[topn].a=a-1; notfinished[topn].b=b-1; notfinished[topn++].weight=c; } else { finished[topf].a=a-1; finished[topf].b=b-1; finished[topf++].weight=c; } } for(i=0;i<n;i++) T[i]=-1; for(i=0;i<topf;i++) { roota=findroot(finished[i].a); rootb=findroot(finished[i].b); if(roota!=rootb) T[rootb]=roota; } min=0; www.2cto.com qsort(notfinished,topn,sizeof(notfinished[0]),cmp); for(i=0;i<topn;i++) { roota=findroot(notfinished[i].a); rootb=findroot(notfinished[i].b); if(roota!=rootb) { T[rootb]=roota; min+=notfinished[i].weight; } } printf("%d\n",min); scanf("%d",&n); } }
