本文共 915 字，大约阅读时间需要 3 分钟。
经典的修公路问题，N个村落进行修路，最后使得修路耗资最少，也就是最小生成树问题。
本题是给你一个N个节点的无向图,以及它的距离矩阵.现在要你求该图的最小生成树,并输出该树中最长边的长度.最长边也就是最后加进去的那条边了。顺其自然，Krustkal算法：
Krustkal算法AC代码：
#include#include #include #include using namespace std;#define MAX 505struct edge { int u, v, cost; };bool cmp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; }vector 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);//unite res += 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
转载地址：http://yuyci.baihongyu.com/