#include<stdio.h>
__int64 Prim(int ma[101][101],int n)
{
	int i,j,k,min;
	__int64 result=0;
	int cost[101],bo[101]={0};
	bo[1]=1;
	for(i=2;i<=n;i++)
		cost[i]=ma[1][i];
	for(i=1;i<n;i++){
		min=100001;
		for(j=2;j<=n;j++)
			if(!bo[j]&&cost[j]<min){
				k=j;
				min=cost[j];
			}
		result+=min;
		bo[k]=1;
		for(j=2;j<=n;j++)
			if(!bo[j]&&cost[j]>ma[k][j])
				cost[j]=ma[k][j];
	}
	return result;
}

int main()
{
	int ma[101][101];
	int i,j,n;
	while(scanf("%d",&n)!=EOF){
		if(!n)
			return 0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&ma[i][j]);
		printf("%I64d\n",Prim(ma,n));
	}
	return 0;
}

• Re:看了各位大虾的提示，终于AC了……贡献了3次wa……顺便问下0ms怎么出来的啊？ (1118) dreamvtkd 2009-09-13 12:22:32