草地排水（最大流）

形式化题目

给定一张有向图： $M$ 个点（ $2 \leqslant M \leqslant 200$ ）、 $N$ 条边（ $0 \leqslant N \leqslant 200$ ），第 $i$ 条边从 $S_i$ 指向 $E_i$ ，容量为 $C_i$ （ $0 \leqslant C_i \leqslant 10^7$ ）。可能存在平行边（两点之间多条边）与环。每条边上流动的量不能超过其容量，且除源汇外每个点流入量等于流出量。求从点 1（源）到点 $M$ （汇）的最大流。

正解

思路

从朴素贪心到残量网络。 最直接的想法是：找一条从 1 到 $M$ 的路径，沿它推送"路径上最小容量"那么多水，重复直到没有路。但这样的贪心会犯错——先推的水可能堵死更优的组合。例如样例里，如果先把 1→2→4 的 20 全推给上面那条路，2→4 就满了；好在正确答案中 1→2 的 40 可以改走 2→3→4。我们需要一种"反悔"机制。

网络流的经典做法是残量网络 + 反向边：每沿边 $u \to v$ 推送 $f$ 单位水，就把 cap[u][v] 减 $f$ ，同时把 cap[v][u] 加 $f$ 。这条反向边代表"已推送的水可以退回来改道"。增广路定理保证：只要残量网络上还存在从源到汇的路径，就还能增大流量；不存在时就达到了最大流（同时等于最小割的容量）。

Dinic 的两层加速。 朴素的 Ford–Fulkerson 每次只找一条增广路，最坏情形会被低效路径拖慢。Dinic 加了两个标准优化：

分层图：每轮开始时 BFS 一遍残量网络，算出每个点到源的层次（最短边数）。之后 DFS 只允许从层次 $d$ 的点走到层次 $d+1$ 的点，保证所有增广都沿"最短路"进行。
当前弧优化：每个点记录"这一轮已经试到第几条邻接边"，被证明推不动的边不再重试。

每轮分层后，可以在同一张层次图上连续推送多条路径，直到沿层次图走不到汇点。汇点的层次每轮严格增加，所以最多 $O(V)$ 轮。

本题的输入形态。 平行边直接累加到 cap[s][e]；自环（ $S = E$ ）不影响任何割，直接跳过；容量为 0 的边在 BFS 时被残量判断自然过滤。

下面的 Graphviz 图展示样例两轮分层增广后的结果（节点 label 为"交点:最终层次"，边 label 为"容量/剩余"，虚线为反向边）：

digraph ditch {
  rankdir=LR;
  node [shape=circle];

  s [label="1:0"];
  a [label="2:1"];
  b [label="3:2"];
  t [label="4:3"];

  s -> a [label="40/10", color=blue];
  s -> t [label="20/0", color=blue];
  a -> t [label="20/0", color=blue];
  a -> b [label="30/20", color=blue];
  b -> t [label="10/0", color=blue];
  t -> a [label="50", style=dashed];
  a -> s [label="50", style=dashed];
}

图后观察重点：第 1 轮 BFS 分层得到层次 $1{:}0,\ 2{:}1,\ 3{:}2,\ 4{:}2$ ，DFS 只走层次 +1 的边，所以推的是 1→2→4 的 20 和 1→4 的 20（3→4 因层次不递增暂时走不到）；第 2 轮在残量网络上 4 的层次升到 3，沿 1→2→3→4 再推 10，3→4 的 10 是唯一瓶颈。合计 $20+20+10=50$ 。虚线反向边记录已推送的流量：如果某一轮走了次优路径，后续可以沿反向边把水"退回"改道，这正是贪心不出错的原因。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-01 06:00
# update_at: 2026-10-01 06:00

import sys
from collections import deque

INF = 1 << 60
level: list[int] = []  # 层次图：每个点在残量网络上的层次，-1 = 未访问
it: list[int] = []     # 当前弧：每个点下一次要尝试的邻接点下标


def bfs(cap: list[list[int]], s: int, t: int) -> bool:
    """在残量网络上从 s 分层，返回汇点 t 是否仍可达（还有增广路）。"""
    global level
    level = [-1] * len(cap)
    level[s] = 0
    queue = deque([s])
    while queue:
        u = queue.popleft()
        for v, c in enumerate(cap[u]):
            if c and level[v] < 0:  # 该排水沟还有残量且对端没分过层
                level[v] = level[u] + 1
                queue.append(v)
    return level[t] >= 0


def dfs(cap: list[list[int]], u: int, t: int, f: int) -> int:
    """沿层次图从 u 向 t 推一条不超过 f 的流，返回实际推送量。"""
    if u == t:
        return f
    while it[u] < len(cap):
        v = it[u]
        advance = cap[u][v] > 0 and level[v] == level[u] + 1  # 只走层次+1 的残量边
        if advance:
            pushed = dfs(cap, v, t, min(f, cap[u][v]))
            if pushed:
                cap[u][v] -= pushed  # 正向边扣残量，反向边留出可回退的容量
                cap[v][u] += pushed
                return pushed
        it[u] += 1  # 这条边再也推不动，当前弧后移
    return 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 邻接矩阵存容量：平行边直接累加；起点=终点的自环不贡献流量
    cap = [[0] * m for _ in range(m)]
    for _ in range(n):
        s, e, c = next(data), next(data), next(data)
        if s != e:
            cap[s - 1][e - 1] += c

    flow = 0
    while bfs(cap, 0, m - 1):  # 水潭 0 → 小溪 m-1
        global it
        it = [0] * m
        while pushed := dfs(cap, 0, m - 1, INF):
            flow += pushed
    print(flow)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-06 10:44
 * update_at: 2026-10-06 10:44
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 205;
const ll INF = (1LL << 60);

ll n, m;
ll cap[MAXM][MAXM]; // 残量网络邻接矩阵：cap[u][v] 为 u 到 v 剩余的容量
int level[MAXM];    // 层次图：每个点在残量网络上的最短边数层次，-1 表示未访问
int cur[MAXM];      // 当前弧：每个点下一轮要从哪个邻接点开始尝试

// 在残量网络上从源点 s 分层，返回汇点 t 是否仍可达（即还有增广路）。
bool bfs(int s, int t) {
    for (int i = 1; i <= m; i++) {
        level[i] = -1;
    }
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 1; v <= m; v++) {
            // 该排水沟还有残量且对端尚未分层
            if (cap[u][v] > 0 && level[v] < 0) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] >= 0;
}

// 沿层次图从 u 向汇点 t 推送不超过 f 的流，返回实际推送量。
ll dfs(int u, int t, ll f) {
    if (u == t) {
        return f;
    }
    for (; cur[u] <= m; cur[u]++) {
        int v = cur[u];
        // 只走层次恰好 +1 的残量边
        if (cap[u][v] > 0 && level[v] == level[u] + 1) {
            ll pushed = dfs(v, t, min(f, cap[u][v]));
            if (pushed > 0) {
                cap[u][v] -= pushed; // 正向边扣残量
                cap[v][u] += pushed; // 反向边留出可回退的容量
                return pushed;
            }
        }
    }
    return 0;
}

void solve() {
    ll flow = 0;
    while (bfs(1, m)) { // 水潭 1 为源，小溪 m 为汇
        for (int i = 1; i <= m; i++) {
            cur[i] = 1;
        }
        ll pushed = dfs(1, m, INF);
        while (pushed > 0) {
            flow += pushed;
            pushed = dfs(1, m, INF);
        }
    }
    cout << flow << "\n";
}

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

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        int s, e;
        ll c;
        cin >> s >> e >> c;
        // 平行边直接累加；自环不贡献流量，跳过
        if (s != e) {
            cap[s][e] += c;
        }
    }

    solve();

    return 0;
}

复杂度

时间复杂度：Dinic 为 $O(V^2 E)$ 。本题 $V, E \leqslant 200$ ，实测全部 12 组官方数据在 0.02s 内通过。
空间复杂度：邻接矩阵 $O(V^2)$ ，加上分层与当前弧数组 $O(V)$ ，约 160KB，远低于 128MB 限制。

总结

本题是最大流模板题：排水沟 = 有向容量边，水潭 = 源，小溪 = 汇。
贪心推流会错，反向边提供"反悔"机制，增广路定理保证终止在最大流。
Dinic 用 BFS 分层 + DFS 当前弧做多层增广，复杂度 $O(V^2 E)$ ，对 $N, M \leqslant 200$ 绰绰有余。
实现细节：平行边累加、自环跳过、容量 0 的边自然被过滤。 EOF

草地排水（最大流）

目录

形式化题目

正解

思路

代码

复杂度

总结