题解 | #Jungle Roads#

#include <iostream>
#include <algorithm>
#define MAX_ROAD_COUNT 75
using namespace std;
int char2int(char x){
    //A=0,B=1....Z=25
    if(x>='A'&&x<='Z'){
        return x-'A';
    }
    return -1;
}

class Edge{
public:
    int from,to,cost;
    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    Edge(int f,int t, int c):from(f),to(t),cost(c){
        // printf("edge init para: SRC %d DST %d cost %d\n",from,to,cost);
    };
    Edge(){};
};

int Find(int S[], int x){
    while (S[x] > -1){
        x = S[x];
    }
    return x;   
}

void Union(int S[], int ROOT1, int ROOT2){
    if(ROOT1==ROOT2) return;
    S[ROOT2] = ROOT1;
}

int kruskal(int e_i, Edge *Edges){
    // printf("in p : %p\n",Edges);

    int total_cost = 0;
    int disjoint_set[26];
    for (int i = 0; i < 26; i++) {
        disjoint_set[i] = -1;
    }
    //如果在一个集合就跳过，否则就加入并加cost
    for(int i=0;i<e_i;i++){
        // printf("edge %d para: SRC %d DST %d cost %d\n",i,Edges[i].from,Edges[i].to,Edges[i].cost);

        int root1 = Find(disjoint_set,Edges[i].from);
        int root2 = Find(disjoint_set,Edges[i].to);
        if(root1!=root2){
            total_cost+=Edges[i].cost;
            Union(disjoint_set,root1,root2);
        }
    }
    return total_cost;
}

int main(){
    //准备一个树的双亲表示法的数组，以备并查集使用
    int amount_of_village;
    int e_i = 0; //Edge数组存放位置,顺便保存有几个边
    while (scanf("%d",&amount_of_village)!=EOF){
        int e_i = 0;
        if(amount_of_village==0) break; //输入结束了
        //新的一个图
        Edge Edges[MAX_ROAD_COUNT];  //初始化边表

        //开始读入边数据
        while(true){
            char c;
            c = cin.peek();
            if(c<='9'&&c>='1'){ 
                //如果开始了下一个图，就停止读入边数据
                break; 
            }else if(c>='A'&&c<='Z'){
                //处理边数据
                char char_node_id;
                int edge_count;
                

                cin>>char_node_id>>edge_count; //输出源节点和边数

                int nID = char2int(char_node_id);

                for(int i = 0;i<edge_count;i++){
                    //边信息获取
                    char dst_char_node;
                    int cost;
                    cin>>dst_char_node>>cost;
                    // printf("edge %d para: SRC %d DST %d cost %d\n",e_i+1,nID,char2int(dst_char_node),cost);
                    Edges[e_i++] = Edge(nID,char2int(dst_char_node),cost);
                }

            }else if(c == '\n' || c==' '){
                cin.get(c); //吃掉
                continue;
            }
            else if(c == '0' || c == -1){
                cin.get(c);
                break;
            }else{
                cout<<"err input get: "<< c <<endl;
            }

        }//边数据读入完成
        sort(Edges,Edges+e_i);
        //执行kruskal算法
        // printf("out p : %p\n",Edges);
        int total_cost = kruskal(e_i,Edges);
        cout<<total_cost<<endl;
    }
}