最小生成树
#include<stdio.h> #include<stdlib.h> int m,n,f[27]; struct mapy { int x,y,len; }map[1000]; int cmp(const void *a,const void *b) { return (*(struct mapy *)a).len-(*(struct mapy *)b).len; } int find(int a) { if(a!=f[a]) f[a]=find(f[a]); return f[a]; } void dj() { int sum,i,num; for(i=0;i<27;i++) f[i]=i; qsort(map,m,sizeof(map[0]),cmp); sum=0;num=0; for(i=0;i<m;i++) { if(find(map[i].x)!=find(map[i].y)) { sum=sum+map[i].len; f[find(map[i].x)]=find(map[i].y); num++; } if(num==n-1) break; } printf("%d\n",sum); } int main() { int i,j,t; char ch1,ch2; while(scanf("%d",&n)!=EOF&&n) { m=0; getchar(); for(i=1;i<n;i++) { scanf("%c%d",&ch1,&t); for(j=1;j<=t;j++) { scanf(" %c%d",&ch2,&map[m].len); map[m].x=ch1-'A'; map[m++].y=ch2-'A'; } getchar(); } dj(); } return 0; }