地铁修建

GitHub跳转原题关系图Canvas 关系图返回列表

按工期从小到大加入隧道，1 和 n 首次连通时的工期即为最小瓶颈路径答案。

OJ: shumeng

题目 ID: CSP201703D

难度:普及+/提高-

标签:并查集排序最小瓶颈路图论

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 朴素做法
    2. 阈值二分思想
    3. 排序加并查集
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 nn 个点、mm 条带工期 cc 的无向候选边。选择若干边，使得存在一条从 11 到 nn 的路径，每条隧道由不同公司同时施工，因此线路的完工时间等于路径上所有边的最大工期。求这个最大工期的最小值。

思路

每条边独立同时施工，一条线路的完工时间取决于它最长的段，问题等价于找一条从 11 到 nn、最大边权最小的路径。

朴素做法

小数据可以递归枚举从 11 到 nn 的所有简单路径，记录每条路径的最大边权并取最小值：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
// brute.cpp：小数据暴力解，递归枚举从 1 到 n 的所有简单路径。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

struct Edge {
    int to, cost;
};

vector<Edge> graph[MAXN];
int visited[MAXN];
int n;
int answer = INT_MAX;

void dfs(int x, int current_maximum) {
    if (current_maximum >= answer) {
        return;
    }
    if (x == n) {
        answer = current_maximum;
        return;
    }

    for (int i = 0; i < (int)graph[x].size(); i++) {
        int y = graph[x][i].to;
        if (visited[y]) {
            continue;
        }
        visited[y] = 1;
        dfs(y, max(current_maximum, graph[x][i].cost));
        visited[y] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, cost;
        cin >> u >> v >> cost;
        Edge first = {v, cost};
        Edge second = {u, cost};
        graph[u].push_back(first);
        graph[v].push_back(second);
    }

    visited[1] = 1;
    dfs(1, 0);
    cout << answer << '\n';

    return 0;
}

阈值二分思想

考虑一个阈值 ww：只允许使用工期不超过 ww 的隧道。此时

  • 若 11 与 nn 已经连通，就存在一条每一段都能在 ww 天内完成的线路；
  • 若仍不连通，则任何完工时间不超过 ww 的方案都不存在。

所以答案是使得 11、nn 连通所需的最小阈值 ww。

排序加并查集

把边按工期升序排序，用并查集依次加入每条边。当 11 与 nn 第一次处于同一集合时，当前加入的这条边的工期就是最小可行阈值，也就是答案。

正确性来自两点：

  • 在此之前加入的边工期都更短，但 11、nn 仍不连通，答案不可能比当前工期更小；
  • 加入当前工期的边后连通，说明该工期已经可行。

二者合起来证明当前边权就是最小值。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXM = 200005;

struct Edge {
    int u, v, cost;
};

int parent[MAXN]; // 并查集父节点
Edge edges[MAXM];

// 路径压缩的并查集查找
int find_root(int x) {
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

bool compare_edge(const Edge &left, const Edge &right) {
    return left.cost < right.cost;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }

    // 按工期从小到大加入隧道，1 与 n 首次连通时的当前工期就是答案。
    // 若用不超过 w 的所有隧道能使 1、n 连通，则存在一条最大段长不超过 w 的线路。
    sort(edges + 1, edges + m + 1, compare_edge);
    for (int i = 1; i <= m; i++) {
        int x = find_root(edges[i].u);
        int y = find_root(edges[i].v);
        if (x != y) {
            parent[x] = y;
        }
        if (find_root(1) == find_root(n)) {
            cout << edges[i].cost << '\n';
            return 0;
        }
    }

    return 0;
}

复杂度

  • 时间：排序耗时 O(mlog⁡m)O(m \log m)，并查集合并近似为 O(m)O(m)。
  • 空间：存储边与并查集，空间复杂度为 O(n+m)O(n + m)。

总结

遇到“边同时完成、只关心一条路径何时可用”的问题，先判断目标量是否是路径上的最大边权。把边权看成逐渐提高的可用阈值，就能用排序加并查集直接找出首次连通的时刻，这正是最小瓶颈路的经典做法。