题解 | #Jungle Roads#

#include <iostream>
#include <algorithm>
using namespace std;


struct Edge{
    double from;
    double to;
    double length;
    bool operator<(const Edge& edge) const{
        return length<edge.length;
    }
};

Edge edge[330];//从0开始
int father[26];
int height[26];


void Initial()//每个点都作为根节点，高度都为0
{
    for(int i=0;i<100;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}

int Find(int x)
{
    if(x==father[x])return x;
    return Find(father[x]);
}

void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a!=b)
    {
        if(height[a]>height[b])father[b]=a;
        else  if(height[a]<height[b])father[a]=b;
        else
         {
            father[b]=a;height[a]++;
         }
    }
}

int Kruskal(int n,int enumber)
{
    int answer=0;
    for(int i=0;i<enumber;i++)
    {
        if(Find(edge[i].from)!=Find(edge[i].to))
        {
            Union(edge[i].from,edge[i].to);
            answer+=edge[i].length;
        }
    }
    return answer;
}


int main() {
    int n;
    while (cin >>n) { 
        if(n==0)break;

        int edgenumber=0;
        for(int i=0;i<n-1;i++)
        {
            char from;cin>>from;
            int number;cin>>number;
            if(number==0)continue;
            for(int j=1;j<=number;j++)
            {
                char to;cin>>to;
                int len;cin>>len;
                edge[edgenumber].from=from-'A';
                edge[edgenumber].to=to-'A';
                edge[edgenumber].length=len;
                edgenumber++;
            }
        }
        sort(edge,edge+edgenumber);
        Initial();
        cout<<Kruskal(n,edgenumber)<<endl;
    }
}