做题训练

Zoj1406_Jungle Roads

#include <bits/stdc++.h>
#define N 111
using namespace std;
struct node {
    int u, v, val;
    node() {}
    node(int a, int b, int c) {
        u = a;
        v = b;
        val = c;
    }
    bool operator<(const node &b) const {
        return val < b.val;
    }
};
vector<node> edge;
int bin[N];
int n, t, val;
char x[2], y[2];
void init() {
    for (int i = 0; i <= n; ++i) {
        bin[i] = i;
    }
    edge.clear();
}
int find(int m) {
    while (bin[m] != m)
        m = bin[m];
    return m;
}
int main() {
    while (scanf("%d", &n) != EOF && n)
    {
        getchar();
        init();
        for (int i = 0; i < n - 1; ++i) {
            scanf("%s%d", &x, &t);
            while (t--)
            {
                scanf("%s%d", &y, &val);
                edge.push_back(node(x[0] - 'A' + 1, y[0] - 'A' + 1, val));
            }
        }
        sort(edge.begin(), edge.end());
        long long cur = 0;
        for (int i = 0; i < edge.size(); ++i) {
            int fx = find(edge[i].u);
            int fy = find(edge[i].v);
            if (fx != fy)
            {
                bin[fy] = fx;
                cur += edge[i].val;
            }
        }
        printf("%lld\n", cur);
    }
    return 0;
}