最大流（Ford-Fulkerson）
图算法 · 网络流 · 残量网络 · 最大流 = 最小割
从源到汇最多能送多少
有一张有向图，每条边有一个容量（一秒最多流过多少水）。从源 s往汇 t送水，每条边的流量不能超过容量、每个中间点流入 = 流出。问：最多能送多少？这就是最大流问题，它是任务分配、二分图匹配、图像分割等一大类问题的通用模型。
残量网络与反向边
Ford-Fulkerson 方法：反复找一条从 s 到 t 的增广路（每条边都还有剩余容量），沿路把流推满瓶颈（路径上最小的剩余容量），直到再也找不到增广路。关键在残量网络：每条用了流量的边 u→v 会生出一条容量等于「已用流量」的反向边v→u。它的作用是反悔——如果之前贪心走错了路，后面可以沿反向边把流退回、改道。正因为有反向边，任意顺序找增广路都能得到正确的最大流。
下面固定一张 4 点网络。故意让第一条增广路走「贪心陷阱」 s→a→b→t（占用了中间边 a→b）。点「下一步」逐步看：每条边标「流量/容量」，琥珀是正向增广、红色虚线是反向退流。到第 4 轮，增广路 s→b→a→t 反向经过 a→b，把第 1 轮误走的那 1 单位退回、改道。走到底，最大流 6。右侧代码随每一步同步高亮。
网络：源 s、汇 t，每条边标「流量/容量」（初始全 0）。反复在残量网络找增广路、推满瓶颈，直到再也找不到
1function maxFlow(n: number, edges: [number, number, number][], s: number, t: number): number {
2 const cap = Array.from({ length: n }, () => new Array(n).fill(0));
3 for (const [u, v, c] of edges) cap[u][v] += c; // 残量容量（反向边初始 0）
4 let flow = 0;
5 const dfs = (u: number, pushed: number, vis: boolean[]): number => {
6 if (u === t) return pushed;
7 vis[u] = true;
8 for (let v = 0; v < n; v++) {
9 if (!vis[v] && cap[u][v] > 0) { // 残量 > 0 才能走
10 const d = dfs(v, Math.min(pushed, cap[u][v]), vis);
11 if (d > 0) { cap[u][v] -= d; cap[v][u] += d; return d; } // 增流 + 反向边加残量
12 }
13 }
14 return 0;
15 };
16 for (;;) {
17 const pushed = dfs(s, Infinity, new Array(n).fill(false)); // 找一条增广路
18 if (pushed === 0) break;
19 flow += pushed; // 累加瓶颈
20 }
21 return flow;
22}
源 → 汇s → t
当前流量0 / 最大 6
1 / 10
最大流 = 最小割
增广路：残量网络里一条 s→t 的路径，沿路推满瓶颈。
反向边：
停机：再无增广路即最大流；此时 s 可达集与其余点之间的边就是最小割。
Edmonds-Karp：用 BFS 找最短增广路，迭代次数被界定在 O(VE²)。
反向边：
u→v 用了 f 流量 → 生出 v→u 容量 f，允许退流改道。停机：再无增广路即最大流；此时 s 可达集与其余点之间的边就是最小割。
Edmonds-Karp：用 BFS 找最短增广路，迭代次数被界定在 O(VE²)。
走到底，把 s 能到达的点和其余点切开，被切断的边的容量之和恰好等于最大流——这就是著名的 最大流最小割定理：送得越多，是因为「咽喉」（最小割）就那么宽。本例最小割是 s→a 与 s→b（都被打满 3/3），容量和 6 = 最大流。许多看似无关的问题（二分图最大匹配、项目选择、图像前景背景分割）都能归约成最大流/最小割来解。