View Code of Problem 372

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 32;
int n,k;
struct edge{ 
	int a,b; 
	int v; 
}s[maxn*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;
}