11285772 生成树

链接: https://www.nowcoder.com/practice/66f16470ff01423991a6e098bb406cce

标签: 二分, 并查集, 图, 最小生成树

---

题意

给一张 个点 条边的无向连通带权图，你有恰好 次操作，每次可以将某条边的权值 （操作可以集中在同一条边上）。操作完成后，选出一棵生成树，使得树中边权最小的边尽量大。输出这个最大化的最小边权。

---

思路

二分答案

对答案 进行二分：能否通过不超过 次 操作，构造出一棵所有边权 的生成树？

Check(X) 的判断

固定目标 后，对每条边 （原权值 ）而言：

• 若 ：直接可用，代价为
• 若 ：需要花费 次操作才能使该边达到目标

我们希望用最小总代价构造一棵生成树，贪心策略是优先选代价小的边——这正是 Kruskal 最小生成树的思路：

1. 按 从小到大排序所有边
2. 用并查集执行 Kruskal，累加选中边的代价
3. 若总代价 且成功选出 条边，则 可达

二分范围

• 下界：（边权至少为 1）
• 上界：（把所有操作都加到最大边上也不超过此值）

复杂度

• 二分 次，每次 check （排序）+ （并查集）
• 总体：

注意事项

• 边权和操作次数均可达 ，全部使用 long long
• 代价累加时需提前判断是否已超 ，避免溢出（最坏情况 可超 long long 范围）

---

样例解析

样例 1：3 个点，2 条边（均为 1），K=2。只有一棵生成树（两边都选），把两条边各 +1，最小边为 2，输出 2。

样例 2：5 个点，7 条边，K=3。二分到 X=7：把边 1-2（权值 5）加 3 次变为 8，代价=3≤3。选生成树 {1-2(8), 1-3(改后...)}。实际上选 {2-1(8), 2-3(8), 3-5(7), 2-4(7)} 共 4 条边连通 5 个点，最小边为 7。

---

代码（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge { int u, v; long long w; };

int par[200005];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    par[a] = b; return true;
}

int n, m;
long long k;
vector<Edge> edges;

bool check(long long X) {
    vector<pair<long long, int>> se(m);
    for (int i = 0; i < m; i++)
        se[i] = {max(0LL, X - edges[i].w), i};
    sort(se.begin(), se.end());
    for (int i = 1; i <= n; i++) par[i] = i;
    long long total = 0; int cnt = 0;
    for (auto& [cost, idx] : se) {
        if (unite(edges[idx].u, edges[idx].v)) {
            total += cost; cnt++;
            if (total > k) return false;
            if (cnt == n - 1) break;
        }
    }
    return cnt == n - 1 && total <= k;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    edges.resize(m);
    long long maxW = 0;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        maxW = max(maxW, edges[i].w);
    }
    long long lo = 1, hi = maxW + k, ans = 0;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if (check(mid)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    cout << ans << "\n";
}

---

代码（Java）

import java.util.*;
import java.io.*;

public class Main {
    static int[] par;
    static int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); }
    static boolean unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        par[a] = b; return true;
    }
    static int n, m; static long k;
    static int[] eu, ev; static long[] ew;

    static boolean check(long X) {
        long[][] se = new long[m][2];
        for (int i = 0; i < m; i++) { se[i][0] = Math.max(0L, X - ew[i]); se[i][1] = i; }
        Arrays.sort(se, (a, b) -> Long.compare(a[0], b[0]));
        par = new int[n + 1];
        for (int i = 1; i <= n; i++) par[i] = i;
        long total = 0; int cnt = 0;
        for (long[] p : se) {
            int idx = (int) p[1];
            if (unite(eu[idx], ev[idx])) {
                total += p[0]; cnt++;
                if (total > k) return false;
                if (cnt == n - 1) break;
            }
        }
        return cnt == n - 1 && total <= k;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); k = Long.parseLong(st.nextToken());
        eu = new int[m]; ev = new int[m]; ew = new long[m]; long maxW = 0;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            eu[i] = Integer.parseInt(st.nextToken()); ev[i] = Integer.parseInt(st.nextToken()); ew[i] = Long.parseLong(st.nextToken());
            maxW = Math.max(maxW, ew[i]);
        }
        long lo = 1, hi = maxW + k, ans = 0;
        while (lo <= hi) {
            long mid = (lo + hi) / 2;
            if (check(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1;
        }
        System.out.println(ans);
    }
}