题解 | Jungle Roads

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 char father[30];
struct road {
    char a;
    char b;
    int weight;
    road(char _a, char _b, int weight1) {
        a = _a; b = _b; weight=weight1;
    }
};
void InitT(int n) {
    for (int i = 0; i < n; ++i) {
        father[i] = 'A' + i;
    }
}
int FindT(char u) {
    if (u == father[u- 'A']) { return u-'A'; }
    else {
        return FindT(father[u - 'A']);
    }
}
void UnionT(int u, int v) {
    int uroot = FindT(father[u]);
    int vroot = FindT(father[v]);
    father[vroot] = uroot + 'A';
}
bool compare(road lhs, road rhs) {
    if (lhs.weight < rhs.weight) {
        return true;
    }
    else {
        return false;
    }
}
int main() {
    int n;
    while (scanf("%d\n", &n) != EOF) {
        if (n == 0) { break; }
        InitT(n + 1);
        vector<road> p;
        for (int i = 1; i < n; ++i) {
            char arr[100] = { 0 };
            fgets(arr, 100, stdin);
            string str = arr;
            if (str[2] != '0') {
                for (int j = 3; j < str.size(); ++j) {
                    if (str[j] >= 'A' && str[j] <= 'Z') {
                        char m = str[j];
                        j = j + 2;
                        string temp = "";
                        while (str[j] >= '0' && str[j] <= '9') {temp=temp+ str[j]; ++j; }
                        int c = stod(temp);
                        road e(str[0],m,c);
                        p.push_back(e);
                    }
                }
            }
        }
        int vertex = 0;
        int total = 0;
        sort(p.begin(), p.end(), compare);
        for (int k = 0; k < p.size(); ++k) {
            if (vertex == n - 1) { break; }
            if (FindT(p[k].a) != FindT(p[k].b)) {
                ++vertex;
                UnionT(p[k].a - 'A', p[k].b - 'A');
                total += p[k].weight;
            }
        }
        printf("%d\n", total);
    }
    return 0;
}