题解 | #Jungle Roads#

//土尔逊Torson 编写于2023/07/07
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstdio>
#include <stdlib.h>
#include <map>
#include <algorithm>
#define N 101

using namespace std;

int Total_Costs;

struct Jungle_Roads_dot {
	int from;
	int to;
	int costs;
	inline bool operator < (const Jungle_Roads_dot &r) const {
		return costs < r.costs;
	}
};

vector<Jungle_Roads_dot> Graph_J13701;
map<char, int> Alphabetical;

int father13701[N];
int height13701[N];

void Init13701(int n) {
	for (int i = 0; i < n; ++i) {
		father13701[i] = i;
		height13701[i] = 0;
	}

	Total_Costs = 0;

	for (int i = 0; i < 26; ++i) {
		Alphabetical['A' + i] = i + 1;
	}
}

int find13701(int x) {
	if (x != father13701[x]) {
		father13701[x] = find13701(father13701[x]);
	}
	return father13701[x];
}

void Union13701(int x, int y, int costs) {
	x = find13701(x);
	y = find13701(y);
	if (x != y) {
		Total_Costs += costs;
		if (height13701[x] > height13701[y]) {
			father13701[y] = x;
		}
		else if (height13701[x] < height13701[y]) {
			father13701[x] = y;
		}
		else {
			father13701[x] = y;
			height13701[y]++;
		}
	}
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		Init13701(n);
		Jungle_Roads_dot JRd;

		for (int i = 0; i < n - 1; ++i) {
			getchar();
			char tmp;
			int m;
			scanf("%c %d", &tmp, &m);
			while (m--) {
				char tmp_to;
				int m_costs;
				getchar();
				scanf("%c %d", &tmp_to, &m_costs);
				JRd.from = Alphabetical[tmp];
				JRd.to = Alphabetical[tmp_to];
				JRd.costs = m_costs;
				Graph_J13701.push_back(JRd);
			}
		}

		sort(Graph_J13701.begin(), Graph_J13701.end());

		for (int i = 0; i < Graph_J13701.size(); ++i) {
			Union13701(Graph_J13701[i].from, Graph_J13701[i].to, Graph_J13701[i].costs);
		}
		printf("%d\n", Total_Costs);
		//for (int i = 0; i < 26; ++i) {
		//	printf("%c %d\n", 'A' + i, Alphabetical['A' + i]);
		//}
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")