题解 | #Jungle Roads#

//INPUT这块给我看的头大，意思为先给一个N，之后有N-1行。每行第一字符代表村庄，第二个数字表示此村庄
//与几个村庄相通(有路)。
//eg：A 2 B 12 I 25为与A相连的有两条路，一条通向B，权值为12，另一条通向I，权值为25
#include "stdio.h"
#include "string"
#include "queue"
using namespace std;
struct Edge{
    int x;int y;
    int weight;
};
priority_queue<Edge> myPQueue;
int Father[1000];
int height[1000];

void Init(int N){
    while (!myPQueue.empty())
        myPQueue.pop();
    for (int i = 0; i < N; ++i) {
        Father[i] = i;
        height[i] = 1;
    }
}

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

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

void Union(Edge edge1){
    int x = edge1.x;
    int y = edge1.y;
    int x_father = find(x);
    int y_father = find(y);
    if(height[x_father] > height[y_father]){
        Father[y_father] = x_father;
    } else if (height[x_father] < height[y_father]){
        Father[x_father] = y_father;
    } else{
        Father[y_father] = x_father;
        height[x_father]++;
    }
}

int KrusKal(int N){
    int sum = 0;
    int count = 0;
    while (!myPQueue.empty()){
        if (count == N-1)
            break;
        Edge edge = myPQueue.top();
        myPQueue.pop();
        int city1 = edge.x,city2 = edge.y;
        if (find(city1) != find(city2)){
            Union(edge);
            ++count;
            sum += edge.weight;
        }
    }
    return sum;
}

int main(){
    int N;
    while (scanf("%d",&N)!=EOF){
        getchar();
        if (N == 0)
            break;
        Init(N);//初始化优先队列
        for (int i = 0; i < N-1; ++i) {
            char city1,city2;
            scanf("%c",&city1);
            int count,weight;
            scanf("%d ",&count);
            for (int j = 0; j < count; ++j) {
                scanf("%c",&city2);
                scanf("%d ",&weight);
                Edge edge;
                edge.x = city1-'A';edge.y = city2-'A';
                edge.weight = weight;
                myPQueue.push(edge);
            }
        }//已将所有的边入队
        printf("%d\n",KrusKal(N));
    }
}