题目链接：Sicily 1090

思路：

简单的最小生成树问题，这里用prim算法即可。用visited数组记录每个结点是否已经被访问，即是否已经在最小生成树中。每次从不在最小生成树中的结点中取出一个key值最小的结点放入生成树中，key值表示结点到已经在生成树中点集合的最小距离。每次加入一个结点后更新与它相邻的结点的key值。

代码：

#include <iostream>#include <queue>#include <stdio.h>#include <memory.h>using namespace std;const int MAX = 501;const int MAX_LEN = 65537;int prim_get_longest(int n, int adj[][MAX]);int main() {	int testcases;	cin >> testcases;	while(testcases--){		int n;		cin >> n;		int adj[MAX][MAX];		for (int i = 1; i <= n; ++i) {			for (int j = 1; j <= n; ++j) {				cin >> adj[i][j];			}		}		cout << prim_get_longest(n, adj) << endl;		if(testcases > 0)			cout << endl;	}	return 0;}int prim_get_longest(int n, int adj[][MAX]){	//Post: Using Prim algorithm to find the minimal spanning tree,	// 		and return the longest edge in the tree.	int longest = 0;	bool visited[MAX];	int key[MAX];	memset(visited, false, sizeof(visited));	for (int i = 2; i <= n; ++i) {		key[i] = adj[1][i];	}	visited[1] = true; //root	for (int i = 1; i < n; ++i) {		int u, min = MAX_LEN;		for (int j = 2; j <= n; ++j) {			if(!visited[j] && key[j] < min){				min = key[j];				u = j;			}		}		longest = max(longest, min);		visited[u] = true;		for (int v = 2; v <= n; ++v) {			if(!visited[v] && adj[v][u] < key[v]){				key[v] = adj[v][u];			}		}	}	return longest;}