题解 | #生成树#

题目链接

生成树

题目描述

给定一个 $N$ 个点、 $M$ 条边的带权无向连通图。你有 $k$ 次操作机会，每次操作可以选择一条边，使其权值加 1。目标是在完成所有操作后，找出一棵生成树，使得这棵生成树中边权最小的边的权值尽可能大。

任务是输出这个最大可能的“最小边权”。

解题思路

这是一个典型的“最大化最小值”问题，非常适合使用二分答案的技巧来解决。

我们的目标是找到一个最大的整数 ans，使得我们存在一种方案，通过不超过 $k$ 次操作，让图中存在一棵所有边的权值都 $\ge ans$ 的生成树。 $2_s$ 二分答案框架

我们在一个可能的值域（例如 $[0, 2 \cdot 10^{14}]$ ）中对 ans 进行二分查找。对于二分过程中的每一个猜测值 mid，我们需要一个 check(mid) 函数来判断这个值是否可行。

如果 check(mid) 返回 true，说明 mid 是一个可能达到的“最小边权”，我们应该尝试更大的值，因此 left = mid。
如果 check(mid) 返回 false，说明 mid 太大了，无法达到，我们必须减小目标，因此 right = mid - 1。

check(x) 函数的设计

check(x) 函数的核心是回答：我们能否通过不超过 $k$ 次操作，构造一棵所有边权都 $\ge x$ 的生成树？

要构造一棵所有边权都 $\ge x$ 的生成树，我们只能使用那些“原始边权 $\ge x$ ”或者“可以通过操作提升到 $\ge x$ ”的边。为了以最少的总操作次数连通整个图，我们应该优先选择那些“提升成本”最低的边。这启发我们借鉴 Kruskal 算法的思想。

check(x) 算法步骤如下：

初始化: 创建一个并查集（Union-Find）数据结构。初始化总操作成本 total_cost = 0。
筛选与合并:
- 创建一个列表 cost_edges 用于存放需要提升的边。
- 遍历原图所有边 $(u,v,w)$ ：
  - 如果 $w \ge x$ ，这条边可以免费使用。我们直接用它来连接 $u$ 和 $v$ （如果它们尚未连通）。
  - 如果 $w < x$ ，则将它的提升成本 $x - w$ 和端点 $(u,v)$ 存入 cost_edges。
构建生成树（Kruskal 过程）:
- 将 cost_edges 按照提升成本从小到大排序。
- 遍历排序后的 cost_edges。对于每条边，如果它的两个端点尚未连通：
  - （防溢出检查） 在累加成本前，先判断 total_cost + current_cost 是否会超过 $k$ 。由于 total_cost 和 current_cost 都可能很大，直接相加可能导致溢出。更安全的方式是检查 total_cost > k - current_cost。如果这个条件成立，说明预算不足，直接判定 check(x) 失败。
  - 如果预算充足，则累加成本，并连接这两个端点。
判断可行性:
- 在上述过程结束后，检查图是否完全连通（即并查集中只有一个连通分量）。
- 同时需要保证总成本未超预算。
- 只有两个条件都满足，check(x) 才返回 true。

通过二分查找，我们就能找到满足 check 函数的最大 x。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

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

struct DSU {
    vector<int> parent;
    int components;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        components = n;
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
        }
    }
};

bool check(long long x, int n, long long k, const vector<Edge>& edges) {
    DSU dsu(n);
    long long cost = 0;

    vector<pair<long long, pair<int, int>>> cost_edges;
    for (const auto& edge : edges) {
        if (edge.w < x) {
            cost_edges.push_back({x - edge.w, {edge.u, edge.v}});
        } else {
            dsu.unite(edge.u, edge.v);
        }
    }

    sort(cost_edges.begin(), cost_edges.end());

    for (const auto& p : cost_edges) {
        long long current_cost = p.first;
        int u = p.second.first;
        int v = p.second.second;
        if (dsu.find(u) != dsu.find(v)) {
            if (cost > k - current_cost) { // 防溢出检查
                return false;
            }
            cost += current_cost;
            dsu.unite(u, v);
        }
    }
    
    return dsu.components == 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    long long k;
    cin >> n >> m >> k;

    vector<Edge> edges(m);
    long long max_w = 0;
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        max_w = max(max_w, edges[i].w);
    }

    long long low = 0, high = max_w + k, ans = 0;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, n, k, edges)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << ans << endl;

    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static class Edge {
        int u, v;
        long w;
        Edge(int u, int v, long w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }

    static class DSU {
        int[] parent;
        int components;
        DSU(int n) {
            parent = new int[n + 1];
            for (int i = 0; i <= n; i++) parent[i] = i;
            components = n;
        }
        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        void unite(int i, int j) {
            int root_i = find(i);
            int root_j = find(j);
            if (root_i != root_j) {
                parent[root_i] = root_j;
                components--;
            }
        }
    }

    static boolean check(long x, int n, long k, List<Edge> edges) {
        DSU dsu = new DSU(n);
        long cost = 0;

        List<long[]> costEdges = new ArrayList<>();
        for (Edge edge : edges) {
            if (edge.w < x) {
                costEdges.add(new long[]{x - edge.w, edge.u, edge.v});
            } else {
                dsu.unite(edge.u, edge.v);
            }
        }

        Collections.sort(costEdges, (a, b) -> Long.compare(a[0], b[0]));

        for (long[] p : costEdges) {
            long currentCost = p[0];
            int u = (int) p[1];
            int v = (int) p[2];
            if (dsu.find(u) != dsu.find(v)) {
                if (cost > k - currentCost) { // 防溢出检查
                    return false;
                }
                cost += currentCost;
                dsu.unite(u, v);
            }
        }

        return dsu.components == 1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long k = Long.parseLong(st.nextToken());

        List<Edge> edges = new ArrayList<>();
        long maxW = 0;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            edges.add(new Edge(u, v, w));
            maxW = Math.max(maxW, w);
        }

        long low = 0, high = maxW + k, ans = 0;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (check(mid, n, k, edges)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(ans);
    }
}

import sys

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.components = n
    
    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j
            self.components -= 1
            return True
        return False

def check(x, n, k, edges):
    dsu = DSU(n)
    cost = 0
    
    cost_edges = []
    for u, v, w in edges:
        if w < x:
            cost_edges.append((x - w, u, v))
        else:
            dsu.unite(u, v)
            
    cost_edges.sort()
    
    for current_cost, u, v in cost_edges:
        if dsu.find(u) != dsu.find(v):
            if cost > k - current_cost:
                return False
            cost += current_cost
            dsu.unite(u,v)

    return dsu.components == 1

def main():
    try:
        n, m, k = map(int, sys.stdin.readline().split())
        edges = []
        max_w = 0
        for _ in range(m):
            u, v, w = map(int, sys.stdin.readline().split())
            edges.append((u, v, w))
            max_w = max(max_w, w)

        low, high = 0, max_w + k
        ans = 0

        while low <= high:
            mid = (low + high) // 2
            if mid < 0: mid = 0
            if check(mid, n, k, edges):
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
                
        print(ans)
    except (IOError, ValueError):
        pass

if __name__ == "__main__":
    main()

算法及复杂度

算法: 二分答案 + Kruskal + 并查集

算法及复杂度

算法: 二分答案 + Kruskal + 并查集
时间复杂度: $O(M \log M \cdot \log(max_w + k))$
- 二分答案需要 $O(\log(max_w + k))$ 次迭代。
- 在每次 check 函数中，主要开销来自于对“待提升”边的排序，其复杂度为 $O(M \log M)$ 。
空间复杂度: $O(N + M)$ ，用于存储图的边和并查集数据结构。