题解 | #Jungle Roads#

思路很简单，题目有点难懂
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int father[27];

struct Node {
	int from;
	int to;
	int length;
};

void Init(int n)
{
	for (int i = 1; i <= n; i++) {
		father[i] = i;
	}
}

bool compare(Node lhs, Node rhs)
{
	return lhs.length < rhs.length;

}

int Find(int x) {
	if (x != father[x])
		father[x] = Find(father[x]);

	return father[x];
}

void Union(int x, int y,int length ,int & total) {
	x = Find(x);
	y = Find(y);
	if (x != y) {

		total = total + length;
		father[x] = y;
	}


}


int main() {
	int n;
	while (cin >> n) {
		if (n == 0) return 0;
		Init(n);
		vector<Node> vec;
		for (int i = 0; i < n - 1; i++) // 将所有边输入
		{
			char a;
			int b;
			cin >> a >> b;
			int from = a - 'A' + 1;
			char c; int dis;

			for (int j = 0; j < b; j++) {
				cin >> c >> dis;
				Node temp;
				temp.from = from;
				temp.to = c - 'A' + 1;
				temp.length = dis;
				vec.push_back(temp);
			}

		}
		sort(vec.begin(), vec.end(), compare);
		int total = 0;
		for (int i = 0; i < vec.size(); i++) {
			Union(vec[i].from, vec[i].to, vec[i].length, total);
		}
		cout << total << endl;

	}
	
	return 0;

}