题解 | Jungle Roads

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Road{
    int from;
    int to;
    int distance;
};
vector<Road>road;
int father[26];
int height[26];
void initial(int n){
    for(int i=1;i<=n;i++){
       father[i]=i;
       height[i]=0;
    }
    return ;
}
bool compare(Road a,Road b){
    return a.distance<b.distance;
}
int Find(int a){
    if(father[a]==a) return a;
    return father[a]=Find(father[a]);
}
void Union(int x,int y){
    int rootx=Find(x);
    int rooty=Find(y);
    if(rootx!=rooty){
        if(height[rootx]<height[rooty]){
            father[rootx]=rooty;
        }else if(height[rootx]>height[rooty]){
            father[rooty]=rootx;
        }else{
            father[rootx]=rooty;
            height[rooty]++;
        }
    }
    return ;
}
int kruskal(int cityNum){
    //  初始化
    initial(cityNum);
    //  边进行排序
    sort(road.begin(),road.end(),compare);
    int res=0;
    for(auto it=road.begin();it!=road.end();it++){
         if(Find(it->from)!=Find(it->to)){
            res+=it->distance;
            Union(it->from, it->to);
         }
    }
    return res;
}
int main() {
   int cityNum;
   while(cin>>cityNum){
    if(cityNum==0) break;
    road.clear();
      int num=cityNum-1;
      while(num--){
        char a,b;
        int roadNum;
        int distance;
        cin>>a>>roadNum;
         for(int i=0;i<roadNum;i++){
            cin>>b>>distance;
            road.push_back({a-'A',b-'A',distance});
         }
      }
      cout<<kruskal(cityNum)<<endl;
   }
   return 0;
}
// 64 位输出请用 printf("%lld")

本质就是kruskal算法，找最小生成树，麻烦的一点就是读入边进行表示