pku2485.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 67 行

#include <stdio.h>
#define SIZ 501

int N;
int dis[SIZ][SIZ];
int mindis[SIZ];
int use[SIZ];

int prim()
{
	int i, j;
	int max, min, minid;
	for (i = 0; i < N; i++)
	{
		use[i] = 0;
		mindis[i] = dis[i][0];
	}

	use[0] = 1;

	for (i = 0, max = 0; i < N - 1; i++)
	{
		min = 1000000;
		for (j = 0; j < N; j++)
		{
			if (use[j] == 0 && mindis[j] < min)
			{
				minid = j;
				min = mindis[j];
			}
		}
		use[minid] = 1;
		if (max < min)
		{
			max = min;
		}
		for (j = 0; j < N; j++)
		{
			if (use[j] == 0 && mindis[j] > dis[j][minid])
			{
				mindis[j] = dis[j][minid];
			}
		}
	}
	return max;
}

int main()
{
	int T, i, j;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &N);
		for (i = 0; i < N; i++)
		{
			for (j = 0; j < N; j++)
			{
				scanf("%d", &dis[i][j]);
			}
		}

		printf("%d\n", prim());
	}
}