题解 | #Jungle Roads#

//本题为北京大学上机题，所以全英文是他最大的难点....
//实际上的话翻译过来本题 就是一个简单的求最小生成树的问题
#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
const int maxn = 110;
using namespace std;
int father[maxn];
int height[maxn];

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

Edge edge[maxn * maxn];

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

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x, int  y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1;
        }
    }
}

int kruskal(int n, int edgeNumber) {
    init(n);
    sort(edge, edge + edgeNumber);
    int sum = 0;
    for (int i = 0; i < edgeNumber; i++) {
        Edge current = edge[i];
        if (find(current.from) != find(
                    current.to)) { //将这条边联通不会产生回环

            Union(current.from, current.to);
            sum += current.length;
        }
    }
    return sum;

}



int main() {
    int n;
    while (cin >> n) {
        if(n==0) break;
        char from,to;
        int f,t,num,weight;
        int edgeNums=0;
        for(int i=1;i<n;i++){
            cin>>from>>num;
            f=from-'A';
            while(num--){
                cin>>to>>weight;
                t=to-'A';
                edge[edgeNums].from=f;
                edge[edgeNums].to=t;
                edge[edgeNums].length=weight;
                edgeNums++;
            }
        }
        cout<<kruskal(n,edgeNums)<<endl;



    }
}