//土尔逊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")