学步园

//poj1251 用Kruskal算法来做 顺带学习并查集 makeset union find 还有qsort用法
#include <iostream>
#include <algorithm>
#define inf 101
using namespace std;

int father[28];
int rank[28];
int sum;
struct edge
{
	int st;
	int ed;
	int w;
}e[400];
int top = 0;
void addEdge(int x, int y, int z)
{
	e[top].st = x;
	e[top].ed = y;
	e[top].w = 	z;
	top++;
}
void makeset(int n)
{
	for(int i = 0; i < n; i++)
	{
		father[i] = i;
		rank[i] = 0;
	}
}
int find(int x)
{
	if(x != father[x])
		father[x] =  find(father[x]);
	return father[x];
}
bool Union(int x, int y)
{
	int t1 = find(x);
	int t2 = find(y);
	if(t1 != t2)
	{
		if(rank[t1] > rank[t2])
		{
			father[t2] = t1;
		}
		else{
			if(rank[t1] == rank[t2])
				rank[t2]++;
			father[t1] = t2;
		}
		return true;	
	}
	return false;
}
int cmp(const void* a, const void* b)
{
	return ((edge*)a)->w - ((edge*)b)->w;
}
int kruskal(int n)
{
	//给边排序
 	qsort(e, top, sizeof(e[0]), cmp);
 	for(int i = 0; i < top; i++)
 	{
	 	if(Union(e[i].st, e[i].ed))
	 	{
	 		sum += e[i].w;
	 	}
	 }
	return sum;
}
int main()
{
	int n;
	cin>>n;
	char a,c;
	int edgeNum;
	int weight1;
	while(n)
	{
		top = 0;
		for(int i = 0; i < n -1 ; i++)
		{
			cin>>a;
			cin>>edgeNum;
			for(int j = 0; j < edgeNum; j++)
			{
				cin>>c;
				cin>>weight1;
				int k = int(c - 'A');
				addEdge(i, k, weight1);
			}
		}
		makeset(n);
		sum = 0;
		cout<<kruskal(n)<<endl;
		cin>>n;
	}
	return 0;	
}