问题：POJ2485
本题求解生成树最大边的最小值
分析：
首先证明生成树最大边的最小值即最小生成树的最大边。
假设：生成树最大边的最小值比最小生成树的最大边更小。
不妨设C为G的一个最小生成树，e是其中的最大边。把e从C中去除，则C被分成C1，C2两个连通子集。假设存在最大边小于e的生成树CC，则CC中连接C1，C2两个点集的桥ee必定小于e。把C中的e换成ee，则 C1,C2,ee必定也生成一个生成树。该生成树长度小于C，与C是最小生成树的事实矛盾，故假设不成立。
因此必有：
生成树最大边的最小值 = 最小生成树的最大边。
故本题转化为求解已知图的最小生成树，用PRIM法即可。
AC代码：
//Memory: 532K Time: 172MS
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
;
int g[maxn][maxn];
bool vis[maxn];
int d[maxn];
int n, t;
int _min, _max;
void prim()
{
memset(vis, , sizeof(vis));
vis[] = ;
;
_max = ;
; i < n; i++){
d[i] = g[][i];
}
while (size < n) {
_min = ;
int k;
; i < n; i++) {
if ( !vis[i] && d[i] < _min) {
_min = d[i];
k = i;
}
}
vis[k] = ;
if (_min > _max) _max = _min;
; i < n; i++) {
if ( !vis[i] && g[i][k] < d[i])
d[i] = g[k][i];
}
size++;
}
}
int main()
{
scanf("%d", &t);
while (t--){
scanf("%d", &n);
; i < n; i++)
; j < n; j++)
scanf("%d", &g[i][j]);
prim();
printf("%d\n", _max);
}
;
}