题解 | #Jungle Roads#

// 求最小生成树
// 克鲁斯卡尔算法kruskal：从边集合中，从小到大筛选，若两端点不属于同一集合，加入该边
// 1.若该图已经连通，退出循环输出结果
// 2.或者循环完所有边，输出结果
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge
{
    int from;
    int to;
    int length;
};

vector<Edge> edge;//装入所有边
int n;
//并查集算法start
const int maxn=27;
int father[maxn];
int height[maxn];
void init(int n){
    for(int i=0; i<n;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}
int find(int x){
    if(x!=father[x]){
        father[x]=find(father[x]);
    }
    return father[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]++;
        }
    }
}
//求连通分量
int countFather(int n){
    int count=0;
    for(int i=0;i<n;i++){
        if(i==find(i))
            count++;
    }
    return count;
}
//并查集算法end

bool comp(Edge x,Edge y){
    return x.length<y.length;
}

void kruskal(int num_of_dot){
    int total=0;
    init(num_of_dot);
    for(auto x:edge){
		//两端点若不都在集合内，加入该边
        if(find(x.from)!=find(x.to)){
            Union(x.from,x.to);
            total+=x.length;
        }
        //如果已经连通，直接输出返回
        if(countFather(num_of_dot)==1){
            cout<<total<<endl;
            return;
        }
    }
    //遍历完所有的边任然不连通
    cout<<total<<endl;
    return;
}

int main(){
    while (cin>>n)
    {
        edge.clear();
        if(n==0) break;
        //输入
        for(int i=0;i<n-1;i++){
            char head,foot;
            int num,number,length;
            cin>>head>>num;
            for(int j=0;j<num;j++){
                cin>>foot>>length;
                Edge e;
                e.from=head-'A';
                e.to=foot-'A';
                e.length=length;
                edge.push_back(e);
            }
        }

        //按边长度从小到大排序
        sort(edge.begin(),edge.end(),comp);

        //克鲁斯卡尔算法
        kruskal(n);
    }
}