题解 | #Jungle Roads#

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int maxn=30;
int father[maxn];
int height[maxn];
bool isCpt(char x){
    if(x>='A' && x<='Z') return true;
    else return false;
}
struct edge{
    int from;
    int to;
    int length;
    edge(char x,char y,int c){
        from=x-'A';
        to=y-'A';
        length=c;
    }
    bool operator< (edge b) const{
        return length>b.length;
    }
};
priority_queue<edge> q;
void init(){
    for(int i=0;i<maxn;i++){
        father[i]=i;
        height[i]=0;
    }
    while(!q.empty()) q.pop();
}
int findf(int x){
    if(x!=father[x]) father[x]=findf(father[x]);
    return father[x];
}
void Union(int x,int y){
    x=findf(x);
    y=findf(y);
    if(x!=y){
        if(height[x]>height[y]) father[y]=x;
        else if(height[x]<height[y]) father[x]=y;
        else{
            father[y]=x;
            height[x]++;
        }
    }
}
int numberin(string x,int& i){
    int r=0;
    while(x[i]!=' '&& i<x.length()){
        r=r*10+x[i]-'0';
        i++;
    }
    return r;
}

int main() {
    int n;
    while(cin>>n && n!=0){
        init();
        getchar();
        while(n>1){
            queue<char> tc;
            queue<int> ti;
            string x;
            getline(cin, x);
            char from=x[0];
            for(int i=1;i<x.length();i++){
                if(x[i]==' ') continue;
                else if(isCpt(x[i])) {
                    tc.push(x[i]);
                }
                else ti.push(numberin(x,i));
            }
            ti.pop();
            while(!tc.empty()){
                q.push(edge(from,tc.front(),ti.front()));
                tc.pop();
                ti.pop();
            }
            n--;
        }
        int cost=0;
        while(!q.empty()){
            edge e=q.top();
            q.pop();
            if(findf(e.from)==findf(e.to)) continue;
            else{
                Union(e.from,e.to);
                cost+=e.length;
            }
        }
        cout<<cost<<endl;

    }
}