引水入城

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

把网格最大流的有限最小割表示为每列分界高度，再用绝对值转移的双向扫描做 DP。

OJ: shumeng

题目 ID: CSP201703E

难度:提高+/省选-

标签:最大流最小割动态规划网格图优化

日期: 2026-07-31 16:21

形式化题目

给定一个 $n \times m$ 的管道网络。第 1 行节点是水源（容量无限取水），第 $n$ 行节点连向城市。纵向管道向下抽水有给定容量、向上放水容量无限；中间各行的横向管道双向抽水、容量给定。求单位时间从顶行送往底行的最大水量。

思路

在小网格上可以直接建立源点、汇点和每个格点，按管道方向连边后用 Dinic 求最大流。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133/**
 * 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：小数据暴力解，建出完整网络后用 Dinic 求最大流。
#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);

struct Edge {
    int to, reverse;
    long long capacity;
};

struct Dinic {
    vector<vector<Edge> > graph;
    vector<int> level, current;

    Dinic(int node_count) : graph(node_count), level(node_count), current(node_count) {}

    void add_edge(int from, int to, long long capacity) {
        Edge forward = {to, (int)graph[to].size(), capacity};
        Edge backward = {from, (int)graph[from].size(), 0};
        graph[from].push_back(forward);
        graph[to].push_back(backward);
    }

    bool bfs(int source, int sink) {
        fill(level.begin(), level.end(), -1);
        queue<int> que;
        level[source] = 0;
        que.push(source);
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            for (int i = 0; i < (int)graph[x].size(); i++) {
                Edge &edge = graph[x][i];
                if (edge.capacity > 0 && level[edge.to] == -1) {
                    level[edge.to] = level[x] + 1;
                    que.push(edge.to);
                }
            }
        }
        return level[sink] != -1;
    }

    long long dfs(int x, int sink, long long flow) {
        if (x == sink) {
            return flow;
        }
        for (int &i = current[x]; i < (int)graph[x].size(); i++) {
            Edge &edge = graph[x][i];
            if (edge.capacity == 0 || level[edge.to] != level[x] + 1) {
                continue;
            }
            long long pushed = dfs(edge.to, sink, min(flow, edge.capacity));
            if (pushed == 0) {
                continue;
            }
            edge.capacity -= pushed;
            graph[edge.to][edge.reverse].capacity += pushed;
            return pushed;
        }
        return 0;
    }

    long long max_flow(int source, int sink) {
        long long answer = 0;
        while (bfs(source, sink)) {
            fill(current.begin(), current.end(), 0);
            while (true) {
                long long pushed = dfs(source, sink, INF);
                if (pushed == 0) {
                    break;
                }
                answer += pushed;
            }
        }
        return answer;
    }
};

long long next_value(long long &x, long long a, long long b, long long q) {
    x = (a * x + b) % q;
    return x;
}

int get_id(int row, int column, int m) {
    return (row - 1) * m + column - 1;
}

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

    int n, m;
    long long a, b, q, x;
    cin >> n >> m >> a >> b >> q >> x;

    int source = n * m;
    int sink = source + 1;
    Dinic dinic(sink + 1);
    for (int column = 1; column <= m; column++) {
        dinic.add_edge(source, get_id(1, column, m), INF);
        dinic.add_edge(get_id(n, column, m), sink, INF);
    }
    for (int row = 1; row <= n - 1; row++) {
        for (int column = 1; column <= m; column++) {
            long long capacity = next_value(x, a, b, q);
            int upper = get_id(row, column, m);
            int lower = get_id(row + 1, column, m);
            dinic.add_edge(upper, lower, capacity);
            dinic.add_edge(lower, upper, INF);
        }
    }
    for (int row = 2; row <= n - 1; row++) {
        for (int column = 1; column <= m - 1; column++) {
            long long capacity = next_value(x, a, b, q);
            int left = get_id(row, column, m);
            int right = get_id(row, column + 1, m);
            dinic.add_edge(left, right, capacity);
            dinic.add_edge(right, left, capacity);
        }
    }

    cout << dinic.max_flow(source, sink) << '\n';

    return 0;
}

但正式网格有 $5000 \times 5000$ 个节点，不能建完整网络。改从最大流最小割看结构。

最小割的形状

源点连着整条顶行、整条底行连着汇点，所以任意有限割中顶行必须在源点侧、底行必须在汇点侧。更关键的是每条竖管自下向上的容量无限：若某列中较低节点在源点侧而它上方节点在汇点侧，就会割到无限边。因此第 $j$ 列的源点侧只能是一个前缀。

令 $h_j \ (1 \le h_j < n)$ 表示第 $j$ 列在第 $h_j$ 行和第 $h_j+1$ 行之间切断。这样一个有限割完全由 $m$ 个高度描述：

纵向代价是第 $j$ 列第 $h_j$ 条向下管道的容量，记为 $V_j[h_j]$ 。
相邻列的高度不同，会切断高度之间的横管。令 $P_j[h]$ 是第 $j$ 与 $j+1$ 列之间、从第 2 行累加到第 $h$ 行的横管容量，约定 $P_j[1]=0$ ，则横向代价为 $|P_j[h_j]-P_j[h_{j+1}]|$ 。

DP 转移

设 $dp[j][h]$ 为处理完前 $j$ 列且第 $j$ 列高度为 $h$ 的最小割。初值为：

dp[1][h]=V_1[h]

跨过第 $j-1$ 条列间边时：

dp[j][b]=V_j[b]+\min_a\{dp[j-1][a]+|P_{j-1}[a]-P_{j-1}[b]|\}

绝对值转移优化

直接枚举 $a, b$ 是 $O(n^2 m)$ 。由于 $P$ 随高度单调不减，对固定 $b$ 把绝对值拆成两半：

\begin{aligned} a\le b &: P[b]+\min_{a\le b}(dp[a]-P[a])\\ a\ge b &: -P[b]+\min_{a\ge b}(dp[a]+P[a]) \end{aligned}

从上到下维护第一式的前缀最小值、从下到上维护第二式的后缀最小值，即可在 $O(n)$ 时间完成一列转移。

样例分界高度 DP 表

表中 $dp[j][h]$ 表示前 $j$ 列的最小割代价，且第 $j$ 列在第 $h$ 行与第 $h+1$ 行之间切断。

已处理列数	$h=1$	$h=2$
1	16	12
2	25	21
3	43	38

例如从第 1 列转到第 2 列时，横向前缀为 $(0, 2)$ ： $dp[2][1]=11+\min(16+0, 12+2)=25$ ， $dp[2][2]=9+\min(16+2, 12+0)=21$ 。最后取最后一列所有高度的最小值，得到样例答案 $38$ 。

输入给出的容量按行生成，而 DP 按列访问。代码将竖管和横管容量分别转置保存为 int 数组，再逐列计算，避免构造任何流网络。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/**
 * 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 long long INF = (1LL << 62);

// 递推生成下一个伪随机数 X_{i+1} = (A*X_i + B) mod Q
long long next_value(long long &x, long long a, long long b, long long q) {
    x = (a * x + b) % q;
    return x;
}

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

    int n, m;
    long long a, b, q, x;
    cin >> n >> m >> a >> b >> q >> x;

    // 容量按行生成、DP 按列使用，因此转置存储。
    // vertical[column*n + row]：第 column 列、row 与 row+1 行之间的竖管容量。
    // horizontal[column*n + row]：第 column 与 column+1 列之间、第 row 行的横管容量。
    long long vertical_size = 1LL * (m + 1) * n;
    long long horizontal_size = 1LL * m * n;
    int *vertical = new int[vertical_size];
    int *horizontal = new int[horizontal_size];

    // 竖管：第 1..n-1 行、每列 m 条，对应数列的前 (n-1)m 项
    for (int row = 1; row <= n - 1; row++) {
        for (int column = 1; column <= m; column++) {
            vertical[1LL * column * n + row] = (int)next_value(x, a, b, q);
        }
    }
    // 横管：第 2..n-1 行、每行 m-1 条，对应数列的接下来 (n-2)(m-1) 项
    for (int row = 2; row <= n - 1; row++) {
        for (int column = 1; column <= m - 1; column++) {
            horizontal[1LL * column * n + row] = (int)next_value(x, a, b, q);
        }
    }

    // dp[h]：当前列在第 h 行与 h+1 行之间切断时的最小割代价。
    // 第一列没有横向代价，初值就是本列竖管容量。
    vector<long long> dp(n), next_dp(n), prefix(n);
    for (int height = 1; height <= n - 1; height++) {
        dp[height] = vertical[n + height];
    }

    for (int column = 2; column <= m; column++) {
        // prefix[h]：第 column-1 与 column 列之间，从第 2 行累加到第 h 行的横管容量
        prefix[1] = 0;
        for (int height = 2; height <= n - 1; height++) {
            prefix[height] = prefix[height - 1]
                    + horizontal[1LL * (column - 1) * n + height];
        }

        // dp[col][b] = V[col][b] + min_a{ dp[col-1][a] + |P[a] - P[b]| }。
        // 绝对值按 a<=b / a>=b 分成两半，各用一次前缀/后缀最小值完成转移。
        long long best = INF;
        for (int height = 1; height <= n - 1; height++) {
            best = min(best, dp[height] - prefix[height]);
            next_dp[height] = best + prefix[height];
        }
        best = INF;
        for (int height = n - 1; height >= 1; height--) {
            best = min(best, dp[height] + prefix[height]);
            next_dp[height] = min(next_dp[height], best - prefix[height]);
            next_dp[height] += vertical[1LL * column * n + height];
        }
        dp.swap(next_dp);
    }

    // 最后一列取所有高度的最小值
    long long answer = INF;
    for (int height = 1; height <= n - 1; height++) {
        answer = min(answer, dp[height]);
    }
    cout << answer << '\n';

    delete[] vertical;
    delete[] horizontal;
    return 0;
}

复杂度

时间：容量生成和 DP 都遍历每条网格管道一次，时间复杂度为 $O(nm)$ 。
空间：两个转置的容量数组使用 $O(nm)$ 空间，最大规模下约为 200MB；另有 $O(n)$ 的 DP 数组。

总结

大网格最大流不一定要建图。先观察无限容量边如何限制有限最小割的形状，再把割边界参数化为一维状态；这里相邻状态的代价恰为单调前缀和之差，才能把二次转移降为双向扫描。

图示解析

这张图串起本题从管网到线性 DP 的主线：

text

1
2
3
4
5
6
7
8并行施工的最大引水量
`- 最大流最小割
   `- 向上放水边容量无穷大
      `- 每列的有限割只能是“上方保留、下方切断”
         |- 选择每列分界高度 h
         |- 纵向代价：切一条竖管
         `- 横向代价：相邻高度之间的横管前缀和之差
            `- 左右扫描优化绝对值转移，O(nm)

无穷大的反向竖边排除了分界线向下再回到源侧的形状，所以一个最小割可以完全由每列一个高度描述。高度相邻时的费用是两个单调前缀和的绝对差，因而不必枚举全部前驱高度。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

MF 城建立在一片高原上。由于城市唯一的水源是位于河谷地带的湖中，人们在坡地上修筑了一片网格状的抽水水管，以将湖水抽入城市。如下图所示：

这片管网由 $n$ 行 $m$ 列节点（红色，图中 $n = 5,\ m = 6$ ），横向管道（紫色）和纵向管道（橙色）构成。

行和列分别用 $1$ 到 $n$ 的整数和 $1$ 到 $m$ 的整数表示。第 $1$ 行的任何一个节点均可以抽取湖水，湖水到达第 $n$ 行的任何一个节点即算作引入了城市。

除第一行和最后一行外，横向相邻或纵向相邻的两个节点之间一定有一段管道，每一段管道都有各自的最大的抽水速率，并需要根据情况选择抽水还是放水。对于纵向的管道（橙色），允许从上方向下方抽水或从下方向上方放水；如果从图中的上方向下方抽水，那么单位时间内能通过的水量不能超过管道的最大速率；如果从下方向上方放水，因为下方海拔较高，因此可以允许有任意大的水量。对于横向的管道（紫色），允许从左向右或从右向左抽水，不允许放水，两种情况下单位时间流过的水量都不能超过管道的最大速率。

现在 MF 城市的水务负责人想知道，在已知每个管道单位时间容量的情况下，MF 城每单位时间最多可以引入多少的湖水。

输入格式

从标准输入读入数据。

由于输入规模较大，我们采用伪随机生成的方式生成数据。

每组数据仅一行包含 6 个非负整数 $n, m, A, B, Q, X_0$ 。其中， $n$ 和 $m$ 如前文所述，表示管网的大小，保证 $2 ≤ n, m ≤ 5000$ ；保证 $1 ≤ A, B, Q, X_0 ≤ 10^9$ 。

$A,B,Q,X_0$ 是数据生成的参数，我们用如下的方式定义一个数列 $\{X_i\}$ ：

X_{i+1}=(AX_i+B)\bmod Q\quad(i\ge 0)

我们将数列的第 $1$ 项到第 $(n-1)m$ 项作为纵向管道的单位时间容量，其中 $X_{(s-1)m+t}$ 表示第 $s$ 行第 $t$ 列的节点到第 $s+1$ 行第 $t$ 列管道单位时间的容量；将数列的第 $(n-1)m+1$ 项到第 $(n-1)m+(n-2)(m-1)$ 项（即接下来的 $(n-2)(m-1)$ 项）作为横向管道的单位时间容量，其中 $X_{(n-1)m+(s-2)(m-1)+t}$ 表示第 $s$ 行第 $t$ 列的节点到第 $s$ 行第 $t+1$ 列管道单位时间的容量。

输出格式

输出到标准输出。

输出一行一个整数，表示 MF 城每单位时间可以引入的水量。

注意计算过程中有些参数可能超过 32 位整型表示的最大值，请注意使用 64 位整型存储相应数据。

input1

13 3 10 3 19 7

output1

样例 1 解释

使用参数得到数列 $\{ X_i \}=\{ 7, 16, 11, 18, 12, 9, 17, 2, 4,\ldots\}$ ，按照输入格式可以得到每个管道的最大抽水量如下图所示：

在标准答案中，单位时间可以引水 38 单位。所有纵向管道均向下抽水即可，不需要横向管道抽水，也不需要向上放水。

input2

12 5 595829232 749238243 603779819 532737791

output2

11029036148

input3

15 2 634932890 335818535 550589587 977780683

output3

1192923706

input4

15 5 695192542 779962396 647834146 157661239

output4

11449991168

子任务

测试点编号	$n=$	$m=$
$1$	$2$	$1000$
$2$	$1000$	$2$
$3$	$1000$	$2$
$4$	$5$	$5$
$5$	$10$	$10$
$6$	$100$	$100$
$7$	$500$	$500$
$8$	$1000$	$1000$
$9$	$2000$	$2000$
$10$	$5000$	$5000$