题意：
给出各个村庄之间路径的距离，同最短的路径走完所有的村庄，就是最小生成树权值的计算，我用了并查集。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct aa{int st,en,quan;
}p[80];
int pre[28],vis[28];bool cmp(aa a,aa b){return a.quan<b.quan;
}
int find(int x) { if (x != pre[x]) { pre[x] = find(pre[x]); //这个回溯时的压缩路径是精华 } return pre[x];
} // return pre[x] == x?x:pre[x] = find(pre[x]); int main(){int n,ss,co,to,sum;char te,fe;while(scanf("%d",&n)&&n){for(int i=0;i<28;i++)pre[i]=i;memset(vis,0,sizeof(vis));to=0;sum=0;for(int i=0;i<n-1;i++){cin>>te>>co;for(int j=0;j<co;j++){p[to].st=te-'A';cin>>fe;p[to].en=fe-'A';cin>>p[to].quan;// vis[te-'a']=vis[fe-'a']=1;to++;}}sort(p,p+to,cmp);for(int i=0;i<to;i++){int x=p[i].st,y=p[i].en;x=find(x);y=find(y);if(x!=y){sum+=p[i].quan;pre[x]=y;}}cout<<sum<<endl;// cout<<to<<endl;} return 0;
}