题目分析：
经典的修公路问题，N个村落进行修路，最后使得修路耗资最少，也就是最小生成树问题。
本题是给你一个N个节点的无向图,以及它的距离矩阵.现在要你求该图的最小生成树,并输出该树中最长边的长度.最长边也就是最后加进去的那条边了。顺其自然，Krustkal算法：
Krustkal算法AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 505
struct edge { int u, v, cost; };
bool cmp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; }
vector<edge>es;//边集合
int fa[MAX];//并查集
int n;//顶点数
int find(int x) { return fa[x] == -1 ? x : fa[x] = find(fa[x]); }//并查集查找 路径压缩
int kk()
{int cnt=0;sort(es.begin(), es.end(), cmp);//对边进行排序memset(fa, -1, sizeof(fa));//并查集初始化int res = 0;for (int i = 0; i < es.size(); i++){if (find(es[i].u) != find(es[i].v))//不在同一个连通分量{fa[find(es[i].u)] = find(es[i].v);//uniteres += es[i].cost;if (++cnt >= n - 1)return es[i].cost;//最后修的路最长咯}}return -1;
}int main()
{int T; cin >> T;while (T--){es.clear();scanf("%d",&n);for(int i=0;i<n;i++)for (int j = 0; j < n; j++){int dist;scanf("%d", &dist);if (i < j){edge tmp = { i,j,dist };es.push_back(tmp);}}cout << kk()<<endl;}system("pause");
}