POJ 2485 Highways （prim裸題 最小生成樹）

題目意思：

給出了一個圖的鄰接矩陣，要求這個圖的最小生成樹的最長邊的長度。 最小生成樹的裸題。

本題要點：

1、邊稠密，使用 prim算法計算最小生成樹。假設 1 點距離這顆最小生成樹的距離為0，

d[i] 表示 i點和最小生成樹的距離。 prim 算好後，周遊 d[i]，選出最大值，就是這顆樹的最長邊的長度；

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 510;
int a[MaxN][MaxN], d[MaxN], n, T, ans;
bool vis[MaxN];

void prim()
{
	memset(d, 0x3f, sizeof d);
	memset(vis, false, sizeof vis);
	d[1] = 0;
	for(int i = 1; i < n; ++i)
	{
		int x = 0;
		for(int j = 1; j <= n; ++j)
		{
			if(!vis[j] && (0 == x || d[j] < d[x]))
			{
				x = j;
			}
		}
		vis[x] = true;
		for(int y = 1; y <= n; ++y)
		{
			if(!vis[y])
			{
				d[y] = min(d[y], a[x][y]);
			}
		}
	}
	ans = -1;
	for(int i = 1; i <= n; ++i)
	{
		ans = max(ans, d[i]);
	}
}

int main()
{
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j)
			{
				scanf("%d", &a[i][j]);
			}
		prim();
		printf("%d\n", ans);
	}
	return 0;
}

/*
1

3
0 990 692
990 0 179
692 179 0
*/

/*
692
*/