题解 | #Jungle Roads#

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 27 + 3;
const int MAXE = 75 + 5;

class Edge{
public:
	int from;
	int to;
	int length;
	bool operator<(const Edge &e) const {
		return length < e.length;
	}
};

int parent[MAXN];
Edge edge[MAXE];

int Find(int x){
	if(parent[x] < 0){
		return x;
	}
	return Find(parent[x]);
}

bool Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		if(parent[x] > parent[y]){
			parent[x] = y;
		}else if(parent[x] < parent[y]){
			parent[y] = x;
		}else{
			parent[y] = x;
			parent[x]--;
		}
		return true;
	}
	return false;
}

int Kruskal(int n, int edgeNumber){
	sort(edge, edge + edgeNumber);
	memset(parent, -1, sizeof(parent));
	int sum = 0;
	for(int i=0; i<edgeNumber; i++){
		Edge current = edge[i];
		if(Union(current.from, current.to)){
			sum += current.length;
		}
	}
	return sum;
}

int main(){
	int n;
	string s;
	int x;
	while(scanf("%d", &n) != EOF){
		int k = 0;//用来生成edge[] 
		int ntmp = n-1;
		while(ntmp--){
			cin >> s;
			scanf("%d", &x);
			int left = s[0] - 'A';
			int xnum = x;
			while(xnum--){
				cin >> s;
				scanf("%d", &x);
				int right = s[0] - 'A';
				edge[k].from = left;
				edge[k].to = right;
				edge[k++].length = x;
			}	
		}
		printf("%d\n", Kruskal(n, k));
	}
	return 0;
}