[USACO11DEC] RoadBlock S / [USACO14FEB] Roadblock G/S

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

先求出一条从 1 到 N 的最短路。只有这条路上的边加倍后才可能让答案变大，因此枚举这条路上的每条边临时加倍，再重跑 Dijkstra 取最短路增量最大值。

OJ: luogu

题目 ID: P2176

难度:普及+/提高

标签:最短路图论思维

日期: 2026-06-20 04:00

目录

  1. 题意
    1. 样例直觉图
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有一张无向带权图，起点是 1，终点是 N。

现在可以选一条边，把它的长度加倍一次。
要求让 1 -> N 的最短路长度增加得尽可能多，输出这个最大增量。

样例直觉图

这张图展示了“把原最短路上的一条边加倍后，被迫改走别的路”的现象：

graph G {
  rankdir=LR;
  1 -- 3 [label="1"];
  3 -- 4 [label="3", color="red", penwidth=2];
  4 -- 5 [label="2"];
  3 -- 5 [label="7"];
}

如果把红边 3-4 加倍，原来的最短路可能不再最优，答案就会变大。
这说明我们真正关心的是：哪些边有能力把原最短路“挤掉”。

思路

先看一个最直接的小数据暴力：

cpp
// brute.cpp：枚举每一条边，把它长度加倍后用 Floyd 求最短路。
// 只适合小数据，但非常直观，适合帮助理解和对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXM = 5005;
const long long INF = (1LL << 60);

int n, m;
int eu[MAXM], ev[MAXM];
long long ew[MAXM];
long long dist_arr[MAXN][MAXN];

void build_graph(int doubled_edge_id) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist_arr[i][j] = 0;
            }
            else {
                dist_arr[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        long long len = ew[i];
        if (i == doubled_edge_id) {
            len *= 2;
        }

        if (len < dist_arr[eu[i]][ev[i]]) {
            dist_arr[eu[i]][ev[i]] = len;
            dist_arr[ev[i]][eu[i]] = len;
        }
    }
}

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist_arr[i][k] + dist_arr[k][j] < dist_arr[i][j]) {
                    dist_arr[i][j] = dist_arr[i][k] + dist_arr[k][j];
                }
            }
        }
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i] >> ew[i];
    }

    build_graph(0);
    floyd();
    long long original_dist = dist_arr[1][n];

    long long answer = 0;
    for (int i = 1; i <= m; i++) {
        build_graph(i);
        floyd();
        answer = max(answer, dist_arr[1][n] - original_dist);
    }

    cout << answer << '\n';

    return 0;
}

暴力做法就是：

  1. 枚举每一条边
  2. 把它长度临时加倍
  3. 重算 1 -> N 的最短路
  4. 取增量最大值

这个做法最贴近题意，但对大图来说没必要把所有边都试一遍。

关键观察是：

  • 如果某条边不在当前求出的一条最短路上
  • 那么把它加倍之后，这条最短路本身仍然原封不动地存在

既然原来的这条最短路还在，新的最短路长度就不可能变大。
而边长只会变大不会变小，所以新的最短路长度也不可能变小。
因此：

  • 不在这条最短路上的边，加倍后增量一定是 0

所以我们只需要：

  1. 先求一遍 1 -> N 的最短路
  2. 把这条最短路上的边重建出来
  3. 只枚举这些边去加倍

于是主解流程变成：

  1. 第一次 Dijkstra，求原最短路，并记录每个点的前驱边
  2. 从 N 倒着回溯，得到一条完整最短路上的边编号
  3. 对这条路上的每条边：
    • 临时把边权乘 2
    • 再跑一次 Dijkstra
    • 更新答案
    • 恢复边权

最后取所有增量里的最大值即可。

代码

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

const int MAXN = 100 + 5;
const int MAXM = 5000 + 5;
const long long INF = (1LL << 60);

struct HeapNode {
    int u;
    long long dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n, m;

// 无向边信息
int eu[MAXM], ev[MAXM];
long long ew[MAXM];

// 链式前向星存有向边，每条有向边只记录“它对应哪条无向边”
int head[MAXN], to[MAXM * 2], nxt[MAXM * 2], edge_id[MAXM * 2], edge_cnt;

long long dist_arr[MAXN];
bool vis[MAXN];
int parent_node[MAXN];
int parent_edge[MAXN];

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
    }
}

void add_edge(int u, int v, int id) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_id[edge_cnt] = id;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void dijkstra(int start, bool save_parent) {
    for (int i = 1; i <= n; i++) {
        dist_arr[i] = INF;
        vis[i] = false;
        if (save_parent) {
            parent_node[i] = 0;
            parent_edge[i] = 0;
        }
    }

    priority_queue<HeapNode> pq;
    dist_arr[start] = 0;
    pq.push({start, 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        if (vis[u]) {
            continue;
        }
        vis[u] = true;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            int id = edge_id[i];
            long long nd = dist_arr[u] + ew[id];

            if (nd < dist_arr[v]) {
                dist_arr[v] = nd;
                if (save_parent) {
                    parent_node[v] = u;
                    parent_edge[v] = id;
                }
                pq.push({v, nd});
            }
        }
    }
}

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

    cin >> n >> m;
    init_graph();

    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i] >> ew[i];
        add_edge(eu[i], ev[i], i);
        add_edge(ev[i], eu[i], i);
    }

    dijkstra(1, true);
    long long original_dist = dist_arr[n];

    vector<int> path_edges;
    int cur = n;
    while (cur != 1) {
        path_edges.push_back(parent_edge[cur]);
        cur = parent_node[cur];
    }

    long long answer = 0;

    // 关键观察：
    // 如果某条边不在这条最短路上，那么把它加倍后，
    // 原来的这条最短路仍然可走，最短路长度不会变大。
    // 所以只需要枚举这条最短路上的边。
    for (size_t i = 0; i < path_edges.size(); i++) {
        int id = path_edges[i];
        ew[id] *= 2;

        dijkstra(1, false);
        answer = max(answer, dist_arr[n] - original_dist);

        ew[id] /= 2;
    }

    cout << answer << '\n';

    return 0;
}

复杂度

设原最短路长度经过了 L 条边。

第一次求最短路：

  • O(Mlog⁡N)O(M \log N)

之后最多再重跑 L 次 Dijkstra，而 L <= N-1，所以总复杂度是：

  • O(N⋅Mlog⁡N)O(N \cdot M \log N)

在本题 N <= 100, M <= 5000 的范围内完全可行。

空间复杂度：

  • O(N+M)O(N + M)

总结

这题最重要的不是 Dijkstra 本身，而是那个削减枚举范围的观察：

  • 只有一条已知最短路上的边，才有资格让最短路变长

一旦把这一点想清楚，后面就只是：

  • 路径重建
  • 枚举边
  • 重跑最短路

的直接实现。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析