#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int maxn = 30; int n,k; struct edge{ int a,b; int v; }s[maxn]; int pre[maxn]; bool cmp(edge a,edge b){return a.v < b.v;} int Find(int a){ int root = a; int tmp; while(root != pre[root])root = pre[root]; while(a != root){ tmp = a; a = pre[a]; pre[tmp] = root; } return root; } void combine(int a,int b){ int x = Find(a); int y = Find(b); if(x > y) swap(x,y); pre[y] = x; } void kruskal(){ int ans = 0; for(int i=0;i<k;i++){ if(Find(s[i].a)!=Find(s[i].b)){ combine(s[i].a,s[i].b); ans += s[i].v; } } printf("%d\n",ans); } int main(){ int m,c; char a[2],b[2]; while(~scanf("%d",&n)&&n) { k=0; for(int i=0;i<=n;i++) { pre[i]=i; } for(int i=1;i<n;i++) { scanf("%s%d",&a,&m); for(int j=0;j<m;j++) { scanf("%s%d ",&b,&c); s[k].a=a[0]-'A'; s[k].b=b[0]-'A'; s[k++].v=c; } } sort(s,s+k,cmp);//排序 kruskal(); } return 0; } |
Double click to view unformatted code.