#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200;
struct node{
	int x,y,z;
};
int n,a,b,f[N];
char ch,ch1;
node data[N];
bool cmp(node a,node b){
	return a.z<b.z;
}
int get1(int x){
	if(f[x]!=x) f[x]=get1(f[x]);
	return f[x];
}
int main(){
	freopen("poj1251.in","r",stdin);
	
	while(1){
		cin>>n;
		
		if(n==0) break;
		
		int ii=0;
		
		for(int i=1;i<n;++i){
			cin>>ch>>a;
			
			for(int j=1;j<=a;++j){
				cin>>ch1>>b;
				
				ii++;
				data[ii].x=ch-'A'+1;
				data[ii].y=ch1-'A'+1;
				data[ii].z=b;
			}
		}
		
		sort(data+1,data+ii+1,cmp);
		
		//for(int i=1;i<=ii;++i) printf("%d %d %d\n",data[i].x,data[i].y,data[i].z);
		//printf("\n");
		
		for(int i=1;i<=n;++i) f[i]=i;
		int num=0;
		int num1=0;
		ii=1;
		
		while(num1!=n-1){
			int x=get1(data[ii].x);int y=get1(data[ii].y);
			
			if(x==y){
				ii++;
				continue;
			}
			
			else{
				num1++;
				f[y]=x;
				num+=data[ii].z;
				++ii;
			}
			
		}
		
		cout<<num<<endl;
		
	}
	
	return 0;
	
}

• Re:0ms,10点全过，cin和cout (1232) suchuanzhi 2019-11-12 16:59:57
  • Re:0ms,10点全过，cin和cout (927) suchuanzhi 2019-11-12 17:02:30