思路与算法

连通图先要求n-1条边，再最小化最大边权；Kruskal的最后一条合并边给最小瓶颈，区别于库内货车运输的多询问最大瓶颈路径。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

连通n点至少用n-1条边，树即可达到。设Kruskal最后合并的边权为W，在小于W的全部边中图还不连通，因此任何生成树必含至少W的边；所得树又全不超过W。

复杂度

O(m log m+n)时间、O(m+n)空间；并查集递归深度至多n。

易错点

目标是最少边后最小最大边，不是把所有道路改造，也不是输出总权和。 n=1时无需道路，最小非负瓶颈阈值为0，输出0 0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct E {
    int a, b, w;
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto &v : e)
        cin >> v.a >> v.b >> v.w;
    sort(e.begin(), e.end(), [](E a, E b) {
        return a.w < b.w;
    });
    vector<int> p(n + 1);
    iota(p.begin(), p.end(), 0);
    function<int(int)> f = [&](int x) {
        return p[x] == x ? x : p[x] = f(p[x]);
    };
    int cnt = 0, last = 0;
    for (auto v : e) {
        int a = f(v.a), b = f(v.b);
        if (a != b) {
            p[a] = b;
            cnt++;
            last = v.w;
        }
    }
    cout << cnt << ' ' << last << "\n";
}