题解 | 生成树

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct E {
    int u, v;
    i64 w;
};

struct DSU {
    vector<int> p, r;
    DSU(int n = 0) {
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        r.assign(n + 1, 0);
        iota(p.begin(), p.end(), 0);
    }
    int f(int x) {
        return p[x] == x ? x : p[x] = f(p[x]);
    }
    bool uni(int a, int b) {
        a = f(a);
        b = f(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
};

int main() {
    int n, m;
    i64 k;
    cin >> n >> m >> k;
    vector<E> e(m);
    i64 mx = 0;
    for (int i = 0; i < m; ++i) {
        int a, b;
        i64 c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
        mx = max(mx, c);
    }
    // 只排序一次：按原权降序
    sort(e.begin(), e.end(), [](const E & A, const E & B) {
        return A.w > B.w;
    });
    auto ok = [&](i64 X) -> bool {
        DSU d(n);
        i64 need = 0;
        int cnt = 0;
        for (const auto& ed : e) {
            if (d.uni(ed.u, ed.v)) {
                ++cnt;
                if (ed.w < X) {
                    need += (X - ed.w);
                    if (need > k) return false; // 剪枝
                }
                if (cnt == n - 1) break;
            }
        }
        return cnt == n - 1 && need <= k;
    };
    // 二分“生成树中的最小边权”的最大可达值
    i64 L = 0, R = mx + k; // 上界安全
    while (L < R) {
        i64 mid = (L + R + 1) >> 1;
        if (ok(mid)) L = mid;
        else R = mid - 1;
    }
    cout << L << '\n';
    return 0;
}