题解 | #Jungle Roads#

#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int a;
    int b;
    int weigh;

    Edge(char _a, char _b, int _weigh) {
        a = _a - 'A';
        b = _b - 'A';
        weigh = _weigh;
    }
};


bool operator<(Edge lhs, Edge rhs) {
    return lhs.weigh < rhs.weigh;
}

int father[100];
int height[100];

void InitSet(int n) {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}

int FindFather(int u) {
    if (u == father[u]) {
        return father[u];
    } else {
        father[u] = FindFather(father[u]);
        return father[u];
    }
}

void UnionSet(int u, int v) {
    int u_root = FindFather(u);
    int v_root = FindFather(v);
    if (height[u_root] > height[v_root]) {
        father[v_root] = u_root;
    } else if (height[v_root] > height[u_root]) {
        father[u_root] = v_root;
    } else {
        father[v_root] = u_root;
        ++height[u_root];
    }
}

int Kruskal(int n, vector<Edge> &edgeVec) {
    InitSet(n);
    int sum = 0;
    int edgeNum = 0;
    sort(edgeVec.begin(), edgeVec.end());
    for (int i = 0; i < edgeVec.size(); ++i) {
        Edge a = edgeVec[i];
        if (FindFather(a.a) != FindFather(a.b)) {
            UnionSet(a.a, a.b);
            edgeNum++;
            sum += a.weigh;
            if (edgeNum == n - 1) {
                break;
            }
        }
    }
    return sum;
}

int main() {
    int n;//村庄的个数
    while (scanf("%d", &n) != EOF) {
        if (0 == n) {
            return 0;
        }
        vector<Edge> edgeVec;
        for (int i = 0; i < n - 1; ++i) {
            char a;
            cin >> a;
            int m;
            scanf("%d", &m);
            for (int j = 0; j < m; ++j) {
                char b;
                cin >> b;
                int weigh;
                scanf("%d", &weigh);
                Edge e(a, b, weigh);
                edgeVec.push_back(e);
            }
        }
        printf("%d\n", Kruskal(n, edgeVec));

    }
    return 0;
}