题解 | #Jungle Roads#

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=30;
int father[N];
int height[N];
struct Edge{
    int from,to;
    int dis;
}edge[80];
bool cmp(Edge a,Edge b){
    return a.dis<b.dis;
}
void Initial(){
    for(int i=0;i<N;i++){
        father[i]=i; 
        height[i]=0;
    }
}
int Find(int x){
    while(father[x]!=x) x=father[x];
    return 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]++;
        }
    }
    return;
}
int kruskal(int n,int edgeNum){
    int sum=0;
    Initial();
    sort(edge,edge+edgeNum,cmp);
    for(int i=0;i<edgeNum;i++){
        int x=edge[i].from;
        int y=edge[i].to;
        x=Find(x);
        y=Find(y);
        if(x!=y){
            Union(x,y);
            sum += edge[i].dis;
        }
    }
    return sum;
}
int main(){
    int n,dis,num,total=0;
    char chr1,chr2;
    while(cin>>n){
        if(n==0) break;
        total=0;
        for(int j=0;j<n-1;j++){
            cin>>chr1;
            cin>>num;
            for(int i=0;i<num;i++){
                cin>>chr2;
                cin>>dis;
                edge[total].from=chr1-'A';
                edge[total].to=chr2-'A';
                edge[total].dis=dis;
                total++;
            }
        }
        int answer = kruskal(n,total);  //总结点数，总边数
        cout<<answer<<endl;
    }
    return 0;
}