网络流 知识点讲解

🎯 先搞清楚它是什么

📌 考纲要求（网络流）：网络流研究的是「在一个有向图里，从源点 s 往汇点 t 最多能送多少『流』（水、数据、物资都行）」，每条边有容量上限。它是图论里一类强力的『建模工具』：很多看似不相关的题（匹配、割、分配）都能翻译成最大流/最小割来秒。

先建立直觉。把网络想成水管系统：左边是水源 s（源点），右边是用水方 t（汇点），中间一堆管子（边），每条管子标着「最多过多少水」(容量 c)。问题是：从 s 到 t，同一时刻最多能流过去多少水？这个最大值就叫 最大流。

但这里有个坑：水流到中间某个节点后，可能选了一条「现在看很优、其实堵死全局」的路。现实中你可以把水往回拨一点、换条路；算法里也要能「反悔」。能反悔，正是网络流算法正确的核心——下面第②点专门讲它。

⚠️ 网络流不是一种算法，而是一类「问题 + 建模方法」。具体求最大流有 EK、Dinic 等算法；但先理解「流网络」本身，算法才好懂。

🧩 关键规则与结论

① 流网络的三要素与两约束

• 要素：有向图；指定 源点 s、汇点 t；每条边 (u,v) 有 容量 c(u,v)（可为 0，表示没有这条边）；实际流过的是 流量 f(u,v)。
• 容量限制：对每条边，0 ≤ f(u,v) ≤ c(u,v)。流量不能为负、不能超过容量。
• 流量守恒：除 s、t 以外的每个节点，流入总量 = 流出总量（水不囤积在中间节点）。s 只出不进（总流出 = 整个网络的流量），t 只进不出。
• 斜对称性：f(u,v) = -f(v,u)。把「从 u 到 v 流了 x」记成「v 到 u 流了 -x」，方便统一处理。

整个网络的流量 |f| = 从 s 流出的总量 = 流入 t 的总量。

② 残量网络与反向边（最大流正确的核心）

残量网络（residual network） 记录「还能不能再加流量」：对一条已流过 f 的边 (u,v)（容量 c），残量 =

• 正向残量 = c - f（还能再往 u→v 加多少）；
• 反向残量 = f（即开一条 反向边 (v,u)，残量为 f，表示「可以从 v 退回到 u 多少」）。

反向边的意义 = 反悔 / 回退。假设算法先贪心走了一条路，后来发现这条路「占用了某条关键管子、导致总流上不去」。这时通过反向边，可以把之前那部分流「原路退回」，腾出容量让别的更优的路径通过。没有反向边，算法一旦走错就无法纠正，求出的就不是真正的最大流。

一句话记住：正向边记录「还能加」，反向边记录「能退多少」，反向边让算法可以反悔，从而保证最终得到的是全局最大而非局部贪心。

③ 增广路

在残量网络中，找一条从 s 到 t 的路径（路径上每条边的残量都 > 0），这条能再送水的路叫 增广路。把这条路上最小的残量 δ 加到整条路的流量上（正向边残量减 δ、对应反向边残量加 δ），总流量就增加了 δ。反复找增广路、增广，直到残量网络里 s 到 t 不再连通——此时总流就是最大流（这就是最大流最小割定理的算法侧面）。

④ EK 算法（Edmonds–Karp）

每次用 BFS 在残量网络里找一条最短（边数最少）的增广路，然后增广。复杂度 O(V·E²)。BFS 保证每次找的是最短增广路，避免退化的长路径导致复杂度爆炸。实现上用邻接表存边，每条边配一条反向边（下标成对：i 与 i^1）。

⑤ Dinic 算法（竞赛主力）

EK 每次只增广一条路，太慢。Dinic 做了两件事提速：

1. 分层（BFS 建分层图）：从 s 出发 BFS，给每个节点标「距 s 的边数」level。只准沿着 level[v] == level[u] + 1 的边走，相当于把图按距离分层，杜绝绕路，每次 DFS 只在「逐层前进」的分层图里增广。

2. 当前弧优化（current arc）：每个节点记录「这条边之前已经尝试过、且已经满流/无油水可榨」，下次直接从这条边之后继续，不再回头扫已经没用的边。这把「重复扫描无效边」的开销砍掉。

复杂度 O(V²·E)（在二分图上甚至 O(E·√V)）。为什么快：分层保证每次 DFS 增广的层数是最短的、且一次 BFS 后能增广多条不冲突的增广路；当前弧避免同一条边被反复无效访问。分层 = 不绕路；当前弧 = 不重复扫废边，二者叠加才快。

⑥ 最大流最小割定理

最大流的值 = 最小割的容量。割是把节点分成「含 s 的集合 S」和「含 t 的集合 T」后，所有从 S 指向 T 的边的容量之和；最小割就是其中容量和最小的那个。这条定理是网络流「建模后直接要最大流就是最小割」的理论基石（如「最少去掉多少容量能切断 s→t」）。

⑦ 费用流（一句话）

边除了容量还有 单位费用 w。在「最大流」基础上要求总费用最小：每次用 SPFA（或代价非负的 Dijkstra）在残量网络里找一条「费用最短路」来增广，直到无法增广。常用于「最小费用最大流」类题。

⑧ 常见模型

• 二分图最大匹配：左部连 s、右部连 t、中间边容量 1，跑最大流即得最大匹配。
• 最大权闭合子图：依赖关系建模，用最小割求最大权闭合子图（正权连 s、负权连 t，割对应取舍）。

🔍 看一个例子

图：s(1) → A(2) 容量 10；s → B(3) 容量 5；A → B 容量 3；A → C(4) 容量 8；B → C 容量 2；C → t(5) 容量 12。求最大流。

Dinic 思路演示（不用手算每一步，看结论怎么来）：

1. BFS 分层：s=0，A/B=1，C=2，t=3。

2. DFS 沿分层边增广：

- 路 s→A→C→t：瓶颈 min(10,8,12)=8，增广 8。此时 A→C 残量 0，C→t 残量 4，s→A 残量 2。

- 路 s→B→C→t：瓶颈 min(5,2,4)=2，增广 2。B→C 残量 0，C→t 残量 2，s→B 残量 3。

- 路 s→A→B→C→t：A→B 残量 3，B→C 残量 0 → 走不通；但此时若之前 A→C 多占了，可经反向边 A←C 退 2 给 s→B→C……（这正是反向边反悔的体现）。

3. 最终最大流 = 10（s 出发总量 10 + 5 = 15 中，C→t 最多 12，且 A/B 汇入后受 C→t=12 与内部约束，实际可达 10）。

手算小图易错，重点是体会「反向边让流能回退、换更优分配」。上机用 Dinic 模板即可，不要手算大图。

下面这道编程题给出 Dinic 模板（带分层 + 当前弧），可直接套 [洛谷 P3376]：

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 205, M = 10005, INF = 1e9;
int head[N], nxt[M], to[M], cap[M], idx = 1; // idx 从 1 起，边 i 与 i^1 互为反向边
int level[N], cur[N]; // level: 分层；cur: 当前弧
int n, m, s, t;

void add(int u, int v, int w) {        // 加正向边与反向边
    to[++idx] = v; nxt[idx] = head[u]; head[u] = idx; cap[idx] = w;
    to[++idx] = u; nxt[idx] = head[v]; head[v] = idx; cap[idx] = 0; // 反向边初始残量 0
}

bool bfs() {                           // ① 分层：BFS 给每个点标距离
    memset(level, -1, sizeof level);
    queue<int> q; q.push(s); level[s] = 0; cur[s] = head[s];
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (cap[i] > 0 && level[v] == -1) { // 只走残量 >0 的边
                level[v] = level[u] + 1;
                cur[v] = head[v];
                if (v == t) return true;
                q.push(v);
            }
        }
    }
    return level[t] != -1;
}

int dfs(int u, int lim) {               // ② 沿分层图增广
    if (u == t) return lim;
    int flow = 0;
    for (int &i = cur[u]; i; i = nxt[i]) { // ③ 当前弧：i 用引用，跳过已榨干的边
        int v = to[i];
        if (cap[i] > 0 && level[v] == level[u] + 1) {
            int k = dfs(v, min(lim - flow, cap[i]));
            if (k == 0) level[v] = -1;  // 此点已无油水，剪掉
            else { cap[i] -= k; cap[i ^ 1] += k; flow += k; } // 正向减、反向加（反悔）
            if (flow == lim) break;
        }
    }
    return flow;
}

int dinic() {
    int maxflow = 0;
    while (bfs()) maxflow += dfs(s, INF); // 每次分层后多次增广
    return maxflow;
}

int main() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        add(u, v, w);
    }
    cout << dinic() << '\n';
    return 0;
}

注意反向边 cap[i^1] 随增广「加回来」——这就是反悔机制；cur[u] 用引用遍历实现当前弧优化。别写成 cap[v] = cap[u] ^ w 这类错误（位运算异或不是流量运算）。

🪤 常见错误

1. 漏掉反向边 / 反向边容量初始不为 0：最大流正确性的命根子。加边时必须成对加 (u,v,w) 与 (v,u,0)，增广时 cap[i]-=k; cap[i^1]+=k。

2. 把「容量」和「流量」搞混：容量是边能扛的上限（固定），流量是实际流的（会变）。问最大流是问「流量总和上限」，不是容量和。

3. 把 ^ 当减号/赋值写错：书上就有 f[v] = f[u] ^ cap 这类排印错误。^ 是按位异或，不是减号也不是比较。流量运算是普通加减，别被印刷错误带歪。另外 == 写成 = 的赋值错误也常出现，比较时务必用 ==。

4. EK 用 DFS 找路 / Dinic 不分层：EK 用 BFS 保证最短增广路；Dinic 必须先 BFS 分层再 DFS，否则复杂度退化、还可能绕路死循环。

5. 死循环不更新残量：增广后必须减去残量；若某次没找到正残量的路仍反复 BFS，会卡死。以「残量网络 s→t 不连通」为终止条件。

6. 当前弧优化写错导致漏边：cur[u] 要用引用遍历并在 flow==lim 时 break，但别在 break 前把还有残量的边跳过——否则答案偏小。

✅ 自测

1. 流网络的两条约束是什么？斜对称性 f(u,v) = -f(v,u) 有什么用？

2. 残量网络里「反向边」的残量是怎么算出来的？它解决了什么问题？

3. 增广路是什么？为什么反复增广直到不连通就得到最大流（联系最大流最小割定理）？

4. EK 与 Dinic 各用什么找增广路？时间复杂度分别是多少？Dinic 的「分层」和「当前弧」分别避免了什么？

5. 判断题：网络流算法不需要反向边也能求到最大流。（ ）为什么？

6. 下面哪句是错的并改正：(a) cap[i] -= k; cap[i^1] += k; (b) cap[v] = cap[u] ^ w;（提示：^ 是异或）

7. 二分图最大匹配、最大权闭合子图分别怎么用最大流/最小割建模？费用流相比普通最大流多了什么条件？

① 流网络、残量网络与 EK 算法（子模型）

配合编程题 [洛谷 P2740 草地排水]（最大流入门）。

一、再夯实定义

• 源 s 只出不进，汇 t 只进不出，中间点流量守恒。
• 对每条边记录容量 cap 与实际流量 flow。0 ≤ flow ≤ cap。
• 网络总流量 = 从 s 流出的总和 = 流入 t 的总和。

二、残量网络（重点）

对原边 (u,v)（容量 c、已流 f）：

正向残量 c_f(u,v) = c - f        // 还能加多少
反向残量 c_f(v,u) = f            // 能退回多少（反向边）

建图时直接开一对边：add(u,v,w) 同时 add(v,u,0)；增广时 cap[i]-=k; cap[i^1]+=k。反向边就是反悔通道。

三、EK（Edmonds–Karp）

maxflow = 0
while 在残量网络中 BFS 找到 s→t 的增广路:
    δ = 路上最小残量
    对路上每条边: 正向 cap -= δ, 反向 cap += δ
    maxflow += δ
return maxflow

• BFS 保证最短（边数最少）增广路，复杂度 O(V·E²)。
• 实现关键：pre[] 记录前驱边，回溯增广；边成对 i 与 i^1。

四、P2740 要点

经典「草地排水」：多个水源（合并为 s）到汇点 t 的多条边（含重边），求最大流。注意重边要累加容量，用 add 时把重边容量叠加即可。EK 在此数据范围可过，但更推荐直接上 Dinic。

② Dinic：分层图 + 当前弧优化（子模型）

配合编程题 [洛谷 P3376 网络最大流模板]。

一、为什么 EK 不够快

EK 每次 BFS 只增广一条路，大图里增广路多达 O(VE) 条，整体 O(VE²) 在稠密图会超时。Dinic 一次 BFS 后增广多条不冲突的路，并避免重复扫废边。

二、分层（BFS）

从 s 出发 BFS，给点标 level[u] = 距 s 的最短边数。DFS 只允许 level[v] == level[u] + 1 的边——这就把图「分层」，杜绝绕路、保证每次增广的层数是最短的。若 BFS 后 t 不可达，算法结束。

三、当前弧优化（current arc）

每个点 cur[u] 记录「下一条该尝试的边」。DFS 沿 cur[u] 用引用遍历：某条边被榨干（残量 0）或它指向的点已无增广，就往后走，下次不再回来看这条废边。这把 EK 里反复无效扫描同一条边的开销砍掉，是 Dinic 真正快的关键之一。

for (int &i = cur[u]; i; i = nxt[i]) {   // 引用：自动推进当前弧
    int v = to[i];
    if (cap[i] > 0 && level[v] == level[u] + 1) {
        int k = dfs(v, min(lim - flow, cap[i]));
        if (k == 0) level[v] = -1;       // 该点已无增广，剪枝
        else { cap[i] -= k; cap[i^1] += k; flow += k; }
        if (flow == lim) break;
    }
}

四、复杂度

• 一般图 O(V²E)；二分图 O(E·√V)。
• 正确性来自：分层保证最短增广、当前弧保证不重复扫废边、反向边保证可反悔。

五、P3376 要点

模板题：给定 n 点 m 边与 s、t，求最大流。直接套上面的 Dinic（注意 idx 从 1 起使 i^1 成对；重边可合并不强求）。数组大小按 N=205, M≈2*(m+...) 估算，避免越界。

③ 费用流与常见模型（子模型）

配合编程题 [洛谷 P2756 飞行员配对方案问题]（二分图最大匹配）。

一、最大流最小割定理

最大流的值 = 最小割的容量。割 = 把点集分成含 s 的 S 与含 t 的 T 后，所有 S→T 边的容量和；最小割即其中最小者。推论：要「切断 s 到 t 所需去掉的最小容量」= 最大流。这是很多「最少代价分割」题的理论基础。

二、费用流（一句话）

边带单位费用 w，求「在最大流前提下总费用最小」。做法：把 EK/Dinic 里找增广路的 BFS/DFS 换成按费用最短路（SPFA，或非负费用用 Dijkstra）找增广路，每次增广费用最少的路。得到「最小费用最大流」。

三、二分图最大匹配 → 最大流

建模：

源 s → 左部每点（容量 1）
左部 → 右部（原匹配边，容量 1）
右部 → 汇 t（容量 1）

跑最大流，流量值 = 最大匹配数。P2756 就是此模型：英国飞行员（左）与外籍飞行员（右）可搭档，求最多配对。

四、最大权闭合子图 → 最小割

给定点带权（正/负），若选了点 u 就必须选它依赖的点 v（u→v 依赖边）。求权和最大的闭合子图：

正权点连 s（容量 = 权），负权点连 t（容量 = |权|）
原依赖边容量 ∞

最小割对应「取舍」，答案 = 所有正权之和 − 最小割。这是网络流建模的进阶常用套路。

五、选型小结