题解 | #Jungle Roads#

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
//习题11.5
const int maxn=26;//0-25
const int maxint=1000000;
int father[maxn];
int height[maxn];

struct edge{
    int node1;
    int node2;
    int dist;
};

edge graph[maxn*maxn];

//初始化
void initial(){
    for(int i=0;i<=maxn;i++){
        father[i]=-1;
        height[i]=0;
    }
}

//Find

int Find(int x){
    if (father[x]==-1)return x;
    return Find(father[x]);
}
//union
void Union(int x,int y){
    int fx=Find(x);
    int fy=Find(y);
    if (fx==fy)return;
    if(height[fx]>height[fy]){
        father[fy]=fx;
    }
    else if(height[fx]<height[fy]){
        father[fx]=fy;
    }
    else{
        father[fx]=fy;
        height[fy]++;
    }
}


int compare(edge x,edge y){
    return x.dist<y.dist;
}

//核心算法！！
int kruskal(int edgenumber){
    int sum=0;
    for(int i=0;i<edgenumber;i++){
        edge e=graph[i];
        if (Find(e.node1)!=Find(e.node2)){
            Union(e.node1,e.node2);
            sum+=e.dist;
        }
    }
    return sum;
}

int char2int(char c){
    int i=c-'A';
    return i;
}

char int2char(int i){
    char c=i+'A';
    return c;
}

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        initial();
        int tmp=0;
        while(n-->1){
            char c1,c2;int neighbors,w,int1,int2;
            cin>>c1;
            int1=char2int(c1);
            cin>>neighbors;
            while(neighbors--){
                cin>>c2;
                int2=char2int(c2);
                cin>>w;
                graph[tmp].node1=int1;
                graph[tmp].node2=int2;
                graph[tmp].dist=w;
                tmp++;
            }
        }
        //for(int j=0;j<tmp;j++){
          //  cout<<"graph["<<j<<"]="<<graph[j].node1<<","<<graph[j].node2<<","<<graph[j].dist<<endl;
        //}
        sort(graph,graph+tmp,compare);
        int sum=kruskal(tmp);
        cout<<sum<<endl;
    }
    return 0;
}