#include<stdio.h>
#define Max 200
int prime(int village[30][30],int n)
{
	int i,j,k,p,q,wm,min=0;
	p=q=n-1;
	village[q][q]=1;
	for(k=0;k<(n-1);k++)
	{
		wm=Max;
		for(i=0;i<n;i++)
			if(village[i][i]==1)
				for(j=0;j<n;j++)
					if(village[j][j]!=1&&village[i][j]<wm)
					{
						wm=village[i][j];
						p=i;
						q=j;
					}
					village[q][q]=1;
					min+=wm;
					if(p>q) village[p][q]=-village[p][q];
					else village[q][p]=-village[q][p];
	}
	return min;
}
int main()
{
	int k,n,a,b,i,j,vi,min;char huiche[10];
	while(scanf("%d",&n)&&n!=0)
	{
		int village[30][30];
		for(k=0;k<n-1;k++)
		{
			scanf("%s%d",huiche,&a);
			while(a--!=0)
			{
				scanf(" %s%d",huiche,&b);
				vi=(int)huiche[0]-65;
				village[k][vi]=b;
				village[vi][k]=b;
			}
		}
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(village[i][j]<0)
				{
					if(i==j) village[i][j]=0;
					else
					village[i][j]=Max;
				}
		min=prime(village,n);
		printf("%d\n",min);
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
				village[i][j]=-1;
		}

	}
	return 0;
}

• Re:求大神指导（题下面和大家提供的测试数据都过了，还是WA） (1221) 393570442 2011-07-30 16:09:24