C語言源碼： [cpp] #include<stdio.h> #include<stdlib.h> #define maxsize 1000 typedef struct edge { int a,b; int weight; }edge; edge E[maxsize]; int T[27]; 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) { struct edge *aa=(edge *)a; struct edge *bb=(edge *)b; return aa->weight-bb->weight; } int main() { int n,weight,k,i,j,top,roota,rootb,min; char point1,point2; scanf("%d",&n); getchar(); while(n) { top=0; for(i=0;i<n-1;i++) { point1=getchar(); scanf("%d",&k); getchar(); while(k--) { point2=getchar(); getchar(); scanf("%d",&weight); getchar(); E[top].a=point1-'A'; E[top].b=point2-'A'; E[top++].weight=weight; } } qsort(E,top,sizeof(E[0]),cmp); for(i=0;i<n;i++) T[i]=-1; min=0; for(i=0;i<top;i++) { www.2cto.com roota=findroot(E[i].a); rootb=findroot(E[i].b); if(roota!=rootb) { T[rootb]=roota; min+=E[i].weight; } } printf("%d\n",min); scanf("%d",&n); getchar(); } }
