题解 | #Jungle Roads#

#include <stdio.h>
#include<stdlib.h>

struct Edge {
    int from;
    int to;
    int lenght;
};

const int max = 27;
struct Edge edge[max*max];
int father[max];
int height[max];

int cmp(const void* A, const void* B) {
    const struct Edge *a = (const struct Edge*) A;
    const struct Edge *b = (const struct Edge*) B;
    if (a->lenght > b->lenght)
        return 1;
    else if (a->lenght < b->lenght)
        return -1;
    else
        return 0;
}

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

void InitialF(struct Edge edge[], int m){
    for (int i = 0; i < m; i++){
        edge[i].lenght = 101;
    }
}

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

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] < height[b]) {
            father[a] = b;
        } else if (height[a] > height[b]) {
                father[b] = a;
            } else {
                father[a] = b;
                height[a]++;
            }
    }
}

int KrusKal(struct Edge edge[], int m){
    
    //InitialF(edge, m);
    qsort(edge, m, sizeof(edge[0]), cmp);
    int cost = 0;
    for (int i = 0; i < m; i++){
        if(Find(edge[i].from) != Find(edge[i].to)){
            Union(edge[i].from, edge[i].to);
            cost+=edge[i].lenght;
        }
    }
    return cost;
}

int main() {
    char a, a1;
    int b, b1;
    int n;
    //getchar();
    while (scanf("%d", &n) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to
        
        if (n == 0) break;
        int m = n*(n-1)/2;
       
        int count = 0;
        for (int j = 0; j < n - 1; j++) {
            getchar();
           
            scanf("%c %d", &a, &b);
             if (b == 0) continue;
            //scanf("%d", &b);
            //scanf("%c %d", &a, &b);
            //printf("%d ", a);
            for (int i = 0; i < b; i++) {
                getchar();
                scanf("%c %d", &a1, &b1);
               //
                edge[count].from = a-'A';
                edge[count].to = a1-'A';
                edge[count++].lenght = b1;
                //printf("(%d %d)\n", edge[i].from, edge[i].to);
            }
        }
        // for(int i = 0 ; i < count; i++){
        //     printf("(%d %d %d)", edge[i].from, edge[i].to, edge[i].lenght);
        // }
        initial(n);
        printf("%d\n", KrusKal(edge,count));
    }
    return 0;
}