#include <stdio.h>
#include <algorithm>
using namespace std;

struct line
{
	int s,e,len;
}l[10000];

int flag[128];//flag[i]等于1表示第i个点已经加入了连通中

bool cmp(struct line &a,struct line &b)
{
	return a.len < b.len;
}

int main()
{
	int i,j,k,n,len,count;
	__int64 totallen;
	while (scanf("%d",&n) != EOF)
	{
		k = 0;
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				scanf("%d",&len);
				if (i != j)
				{
					l[k].s = i;
					l[k].e = j;
					l[k].len = len;
					k++;
				}
			}
		}
//上面为读入部分
		sort(&l[0],&l[k],cmp);
		memset(flag,0,sizeof(flag));
		flag[l[0].s] = 1;　　　　　　//将最短的一条的一个点放入
		totallen = 0;
		count = 0;
		for (i = 0; i < k; i++)
		{
			if (flag[l[i].s] == 1 && flag[l[i].e] == 0)//判断最短的边的两点的其中一点是否能够放入
			{
				totallen += l[i].len;
				flag[l[i].e] = 1;
				count++;
			}
			else if (flag[l[i].s] == 0 && flag[l[i].e] == 1)
			{
				totallen += l[i].len;
				flag[l[i].s] = 1;
				count++;
			}
			if (count == n - 1)
				break;
		}
		printf("%I64d\n",totallen);
	}
	return 0;
}

• Re:求教高人 (8) orangelegend 2008-08-20 14:44:42
  • Re:求教高人 (19) orangelegend 2008-08-20 14:53:35
    • 搞定了。1258 Accepted 268K 16MS (1018) orangelegend 2008-08-20 15:13:35