[NOIP 2013 提高组] 货车运输

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

先建最大生成森林，把最大瓶颈路径转成树上路径最小边权，再用倍增 LCA 回答询问。

OJ: luogu

题目 ID: P1967

难度:提高+/省选-

标签:最大生成树KruskalLCA倍增图论

日期: 2026-06-22 21:38

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定一张无向带权图，边权表示道路限重。

每次询问两个城市之间最多能运输多重的货物。路径能承载的重量等于路径上最小边权；如果两点不连通，输出 -1。

思路

先看一个可以直接验证想法的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：Floyd 求任意两点最大瓶颈路，只适合小数据对拍。

const int MAXN = 55;

int n, m, q;
int best[MAXN][MAXN]; // best[i][j] 表示 i 到 j 能达到的最大路径瓶颈值。

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            best[i][j] = -1;
        }
        best[i][i] = 1000000000;
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        best[u][v] = max(best[u][v], w);
        best[v][u] = max(best[v][u], w);
    }
}

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (best[i][k] == -1 || best[k][j] == -1) {
                    continue;
                }
                int value = min(best[i][k], best[k][j]);
                if (value > best[i][j]) {
                    best[i][j] = value;
                }
            }
        }
    }
}

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

    read_input();
    floyd();

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << best[x][y] << '\n';
    }

    return 0;
}

暴力可以用 Floyd 求任意两点最大瓶颈路：

text
best[i][j] = max(best[i][j], min(best[i][k], best[k][j]))

但 n 接近 10^4，O(n3)O(n^3) 不能通过。

这道题的关键性质是：任意两点在最大生成树路径上的最小边权，等于原图中这两点的最大瓶颈路径值。

理由可以从 Kruskal 理解：按边权从大到小加入边，两点第一次连通时的边权，就是它们能被大边连通的最高阈值。之后在最大生成森林中，两点之间只有一条树路径，这条路径的最小边权就是答案。

所以做法分两步：

  1. 用 Kruskal 建最大生成森林；
  2. 在森林上用倍增 LCA 查询两点路径最小边权。

预处理时维护：

  • up[x][j]：x 向上跳 2^j 步的祖先；
  • min_edge[x][j]：这段跳跃路径上的最小边权。

查询时如果两点不在同一棵树中，输出 -1。否则先把深度较大的点跳到同一深度，再让两个点一起向上跳到 LCA，沿途对 min_edge 取最小值。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXM = 50005;
const int LOG = 15;
const int INF = 1000000000;

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

int n, m, q;
Edge edge[MAXM];

int father[MAXN];
int head[MAXN], to[MAXN * 2], weight_edge[MAXN * 2], nxt[MAXN * 2], edge_cnt;
int depth_node[MAXN];
int up[MAXN][LOG];
int min_edge[MAXN][LOG]; // min_edge[x][j] 表示 x 向上跳 2^j 条边时经过的最小限重。
int component[MAXN];

bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w > b.w;
}

int find_root(int x) {
    if (father[x] == x) {
        return x;
    }
    father[x] = find_root(father[x]);
    return father[x];
}

bool merge_set(int x, int y) {
    int rx = find_root(x);
    int ry = find_root(y);
    if (rx == ry) {
        return false;
    }
    father[rx] = ry;
    return true;
}

void add_tree_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    weight_edge[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
}

void build_maximum_spanning_forest() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    sort(edge + 1, edge + m + 1, cmp_edge);

    for (int i = 1; i <= m; i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        if (merge_set(u, v)) {
            add_tree_edge(u, v, w);
            add_tree_edge(v, u, w);
        }
    }
}

void bfs_component(int start, int cid) {
    queue<int> que;
    que.push(start);
    component[start] = cid;
    depth_node[start] = 1;
    up[start][0] = 0;
    min_edge[start][0] = INF;

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int j = 1; j < LOG; j++) {
            up[u][j] = up[up[u][j - 1]][j - 1];
            min_edge[u][j] = min(min_edge[u][j - 1], min_edge[up[u][j - 1]][j - 1]);
        }

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == up[u][0]) {
                continue;
            }
            component[v] = cid;
            depth_node[v] = depth_node[u] + 1;
            up[v][0] = u;
            min_edge[v][0] = weight_edge[i];
            que.push(v);
        }
    }
}

void prepare_lca() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < LOG; j++) {
            min_edge[i][j] = INF;
        }
    }

    int cid = 0;
    for (int i = 1; i <= n; i++) {
        if (component[i] == 0) {
            cid++;
            bfs_component(i, cid);
        }
    }
}

int query(int x, int y) {
    if (component[x] != component[y]) {
        return -1;
    }

    int answer = INF;
    if (depth_node[x] < depth_node[y]) {
        swap(x, y);
    }

    int diff = depth_node[x] - depth_node[y];
    for (int j = LOG - 1; j >= 0; j--) {
        if ((diff & (1 << j)) != 0) {
            answer = min(answer, min_edge[x][j]);
            x = up[x][j];
        }
    }

    if (x == y) {
        return answer;
    }

    for (int j = LOG - 1; j >= 0; j--) {
        if (up[x][j] != up[y][j]) {
            answer = min(answer, min_edge[x][j]);
            answer = min(answer, min_edge[y][j]);
            x = up[x][j];
            y = up[y][j];
        }
    }

    answer = min(answer, min_edge[x][0]);
    answer = min(answer, min_edge[y][0]);
    return answer;
}

void solve() {
    build_maximum_spanning_forest();
    prepare_lca();

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << query(x, y) << '\n';
    }
}

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

    read_input();
    solve();

    return 0;
}

复杂度

排序建最大生成森林为 O(mlogm)O(m log m)，LCA 预处理为 O(nlogn)O(n log n)，每次查询为 O(logn)O(log n)。

总时间复杂度为 O(mlogm+nlogn+qlogn)O(m log m + n log n + q log n)，空间复杂度为 O(m+nlogn)O(m + n log n)。

总结

“路径最小边权最大”是最大瓶颈路问题。

当询问很多时，不要每次在原图上重新找路；先用最大生成森林保留所有瓶颈信息，再把问题变成树上路径查询。