题解 | Jungle Roads

#include<iostream>
#include<algorithm>
//题不难，就是读起来无语 A 2 B 12 I 25意思就是A有2条路，A到B一条，成本12，A到I一条，成本25
using namespace std;
const int maxn = 10005;
int f[maxn];
int h[maxn];
void init(){
	for(int i=0;i<maxn;i++){
		f[i] = i;
		h[i] = 0;
	}
}
int find(int x){
	if(x!=f[x]){
		f[x] = find(f[x]);
	}
	return f[x];
}
void uniond(int x,int y){
	x = find(x);
	y = find(y);
	if(x!=y){
		if(h[x]>h[y])f[y] = x;
		else if(h[x]<h[y])f[x] = y;
		else{
			f[y] = x;
			h[x]++;
		}
	}
}
struct edge{
	int from;
	int to;
	int len;
}ed[maxn];
bool cmp(edge e1,edge e2){
	return e1.len<e2.len;
}
int chartoint(char ss){
	return ss-'A';
}
int main(){
	int n;
	while(cin>>n){
		if(n==0)break;
		int k=0;
		for(int i=0;i<n-1;i++){
			char ss,s2;
			int x1,x2;
			cin>>ss>>x1;
			int y1 = chartoint(ss),y2 = 0;
			for(int j=0;j<x1;j++){
				ed[k].from = y1;
				cin>>s2>>x2;
				y2 = chartoint(s2);
				ed[k].to = y2;
				ed[k].len = x2;
				k++;
			}
		}
		init();
		int sum = 0;
		sort(ed,ed+k,cmp);
		for(int i=0;i<k;i++){
			if(find(ed[i].from)!=find(ed[i].to)){
				uniond(ed[i].from,ed[i].to);
				sum+=ed[i].len;
			}
		}
		cout<<sum<<endl;
	}
}