网络流算法：最大流与最小割
网络流算法：最大流与最小割
什么是网络流
网络流是图论中研究在一个有向图中传输“流量”的理论。可以把网络想象成城市供水管道系统：水从水源地出发，通过管道流向目的地，每条管道有最大承载流量。在计算机科学中，网络流可以建模交通网络、数据包路由、资源分配等问题。
一个流网络 (G=(V, E)) 包含：
- 源点 s：流量的起点，只出不进。
- 汇点 t：流量的终点，只进不出。
- 有向边 (u, v)，每条边有一个容量 c(u, v) ≥ 0，代表该边最多能通过多少流量。
- 如果 (u, v) 不是边，则 c(u, v) = 0。
流 是一个函数 f: V×V → R，满足：
- 容量限制：对所有 u,v， 0 ≤ f(u,v) ≤ c(u,v)
- 流量守恒：对除源点汇点外的任意结点 u，流入总量等于流出总量： [ \sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v) ]
网络流的值 |f| 定义为从源点流出的总流量（也就等于流入汇点的总流量）： [ |f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s) ]
最大流问题
最大流问题就是：给定一个流网络，求从源点到汇点的最大可能流量值。
残量网络与增广路
要理解最大流算法，必须先掌握两个核心概念。
残量网络 (G_f)
对于原网络 G 和当前流 f，残量网络表示还有多少剩余容量可以推送流量，以及多少已有流量可以“退回”。
每条边 (u, v) 在残量网络中可能变成两条有向边：
- 正向残量边：容量 (c_f(u, v) = c(u, v) - f(u, v))，表示还能增加多少正向流。
- 反向残量边：容量 (c_f(v, u) = f(u, v))，表示可以取消多少已有的正向流（相当于反向推送流量）。
负向残量边允许算法“撤销”之前的决策，这是正确求解的关键。
增广路径
在残量网络 (G_f) 中，从源点 s 到汇点 t 的一条简单路径，且路径上每条边的残量容量都大于 0。
沿着增广路径推送流量，可以增加网络流的总值。增广量等于路径上最小残量容量。
Ford-Fulkerson 方法
算法思想：只要残量网络中还存在增广路径，就沿着它推送尽可能多的流量，重复直到没有增广路径为止。
伪代码：
Ford-Fulkerson(G, s, t):
初始化所有边流量为 0
while 在残量网络 G_f 中存在从 s 到 t 的路径 P:
找到 P 上的最小残量容量 cf(P)
对 P 上的每一条边 (u, v) 在 G_f 中的对应方向:
如果 (u, v) 是正向边，则 f(u, v) += cf(P)
如果 (u, v) 是反向边，则 f(v, u) -= cf(P) // 实际上是取消之前的部分流量
返回流 f
时间复杂度：依赖于如何寻找增广路径。最坏情况下可能达到 (O(|E| \cdot |f^|))，其中 (|f^|) 是最大流的值，这在流量值很大时不可接受。
Edmonds-Karp 算法
Edmonds-Karp 算法是 Ford-Fulkerson 方法的一个实现：每次用 BFS 在残量网络中找到边数最少的增广路径（最短增广路径）。
- 时间复杂度：(O(V \cdot E^2))，与最大流数值无关，适合整数容量。
- 关键性质：每次增广后，到达每个结点的最短距离（按边数）非递减，因此每个边被选为关键边（即增广路径上容量最小的边）的次数为 O(V) 次，共有 E 条边，总迭代次数 O(VE)。
步骤：
- 初始化 flow = 0，构建残量网络（初始时与原图相同，每条边有容量 c，反向边容量为 0）。
- 在残量网络上从 s 做 BFS，记录父节点和路径，直到到达 t 或没有路径。
- 若到达 t，沿着父节点回溯，找到路径上的最小残量容量 augment。
- 更新路径上所有边的正向残量容量减少 augment，反向残量容量增加 augment；同时累计流量值。
- 重复步骤 2，直到 BFS 无法到达 t。
Dinic 算法
Dinic 算法在稠密图上效率更高，基本思想是分层图 + 阻塞流。
分层网络：从 s 做 BFS，计算出每个结点到 s 的最短距离（边数），记为 level[u]。分层网络 (G_L) 只保留那些满足 level[v] = level[u] + 1 的边 (u, v)。
阻塞流：在分层网络上，不能再增加任何从 s 到 t 的流的流（即所有 s-t 路径至少有一条边达到饱和）。
Dinic 流程：
- BFS 构建分层图。如果 t 不可达，算法结束。
- 在分层图上用 DFS 寻找多条增广路径并推送流量，直到阻塞。
- 重复步骤 1。
DFS 过程中常用“当前弧优化”跳过已经检查过并饱和的边，保证复杂度。
时间复杂度：(O(V^2 E))，在单位容量网络上可达 (O(min(V^{2/3}, E^{1/2}) \cdot E))，实际表现非常快。
最小割问题
割的定义
一个 s-t 割 (S, T) 是将顶点集 V 划分为两个集合，其中 s ∈ S，t ∈ T。
割的容量 (c(S, T)) 定义为所有从 S 指向 T 的边的容量之和： [ c(S, T) = \sum_{u \in S, v \in T} c(u, v) ]
割的净流量 (f(S, T)) 定义为所有从 S 流向 T 的流量减去从 T 流回 S 的流量： [ f(S, T) = \sum_{u \in S, v \in T} f(u, v) - \sum_{u \in S, v \in T} f(v, u) ]
最小割问题：找到所有 s-t 割中容量最小的那个割。
最大流最小割定理
定理：在一个流网络中，最大流的值等于最小割的容量。即： max |f| = min c(S, T)
证明思路：
- 对于任意流 f 和任意割 (S, T)，有 |f| = f(S, T) ≤ c(S, T)。所以任何流的值都不会超过任何割的容量。
- 当 Ford-Fulkerson 算法终止时，残量网络中没有从 s 到 t 的路径。令 S = 从 s 在残量网络中可达的顶点集合，T = V \ S。显然 s∈S，t∈T。
- 对于每条从 S 到 T 的原边 (u, v)，必定有 f(u, v) = c(u, v)，否则残量正向边容量>0，v 也会在 S 中。
- 对于每条从 T 到 S 的原边 (v, u)，必定有 f(v, u) = 0，否则会有反向残量边从 u 到 v 使得 v 可达。
- 因此 |f| = f(S, T) = (\sum_{u\in S, v\in T} c(u, v)) = c(S, T)。此时找到了一个流和一个割，值相等，所以流是最大流，割是最小割。
这个定理不仅揭示了最大流与最小割的对偶性，也给出了找到最小割的方法：在最大流的残量网络中，从 s 出发可达的结点集合就是最小割的 S 集合。
应用场景
二分图匹配
最大流可以解决二分图最大匹配问题。构造网络：
- 源点连接所有左侧结点，容量为 1。
- 所有右侧结点连接汇点，容量为 1。
- 每条左右之间的边容量为 1。 最大流的值即为最大匹配数。
项目选择问题
有若干项目，每个项目有收益 p_i（可能为负，表示成本）。某些项目之间有依赖关系，选择某个项目必须选择另一些。通过最小割建模，可以找到最大化利润的选择方案。构建网络：
- 对于收益正的项目，边 (s, i) 容量 = p_i。
- 对于收益负的项目，边 (i, t) 容量 = -p_i。
- 依赖关系：边 (i, j) 容量 ∞（表示如果选择 i 但不选择 j，割会切断 ∞ 边，不可能成为最小割）。 最大利润 = 所有正收益之和 - 最小割容量。
边连通度与顶点连通度
- 无向图的边连通度：最少割多少条边才能让图不连通。将每条无向边变成两条反向有向边，容量 1，源点为任意结点，枚举其他结点作为汇点求最大流，所有结果的最小值就是边连通度。
- 顶点连通度：需要拆点：将每个顶点 u 分成入点 u_in 和出点 u_out，中间连一条容量为 1 的边；原边对应 u_out -> v_in 容量 ∞。枚举源点汇点求最大流即可。
常见变体与进阶
多源点多汇点
添加一个超级源点，连接所有真实源点，容量为无穷；添加一个超级汇点，所有真实汇点连接它，容量无穷。在新网络上求最大流即可。
顶点容量限制
若每个结点有最大流量通过限制，采用拆点法：把结点 u 拆成 u_in 和 u_out，之间连接一条容量为顶点容量的边。所有进入 u 的边连接到 u_in，从 u 出去的边从 u_out 发出。
最小费用最大流
在边上附加单位流量的费用，目标是先保证最大流，再使总费用最小。常用算法：连续最短增广路（SSP）用 SPFA 或 Dijkstra（结合势函数）寻找单位费用最小的增广路。
带下界的网络流
每条边不仅有容量上限，还有流量下界。需转换为标准最大流问题，通常通过添加附加源汇，构建可行流判断。
实现要点（以 Dinic 为例）
struct Edge {
int to, rev; // 目标点，反向边下标
long long cap;
};
vector<vector<Edge>> graph;
vector<int> level, iter;
void add_edge(int from, int to, long long cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
void bfs(int s) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto &e : graph[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
long long dfs(int v, int t, long long f) {
if (v == t) return f;
for (int &i = iter[v]; i < graph[v].size(); i++) {
Edge &e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
long long d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
long long max_flow(int s, int t) {
long long flow = 0;
while (true) {
bfs(s);
if (level[t] < 0) return flow;
fill(iter.begin(), iter.end(), 0);
long long f;
while ((f = dfs(s, t, LLONG_MAX)) > 0) {
flow += f;
}
}
}
总结
- 最大流问题是在容量限制下从源点到汇点推送尽可能多的流量。
- 残量网络和增广路径是核心抽象，反向边实现取消机制。
- Ford-Fulkerson 方法通过不断增广求解最大流，Edmonds-Karp 使用 BFS 保证多项式时间。
- Dinic 利用分层图和多路增广大幅提升效率，是竞赛和工程中的首选。
- 最大流最小割定理揭示两个问题等价，最小割可由最大流残量网络的源点可达集得到。
- 该理论广泛应用于匹配、连通性、资源分配等领域。
下一步你可以练习解决经典问题，如洛谷 P3376 （最大流模板），或者尝试将实际问题建模为网络流。