网络流最大流与最小割算法

可视化演示

网络流模型

想象水务工程师画一张图：水库是起点，城市是终点，中间的加压站和分岔口都是节点，节点之间用单向管道连接。每条管道上都标着一个数字——它的粗细，也就是每分钟最多能通过多少立方米水。这个带容量标注的有向图，就是流网络的直观形象：它不关心管道里现在有多少水，只关心“最多能放多少水进去”的规则。

计算机里的流网络可以写成严谨的形式：一个流网络是带权有向图 $G=(V,E)$，每条边 $(u,v)$ 有一个非负容量 $c(u,v)$。我们把源点记为 $s$，汇点记为 $t$。定义在边上的流 $f(u,v)$ 描述当前的送水量，它必须遵守两条“水规”：第一，任何管道里的水量不能超过它的管径；第二，除了水库和城市，每个中转站既不能凭空产生水，也不能偷偷存水，流入量必须等于流出量。

理解流网络，就像先看懂供水管网图，你才谈得上调度和防断水。有了这两个约束，任意一组满足条件的 $f$ 就是一个“可行流”，下一节我们就要从中寻找那个最大的送水量。

最大流问题

水务工程师的问题很直接：在不动工改管道的前提下，这套管网每分钟最多能送多少水到城市？这个值叫最大流，记作 $|f|$。因为流量守恒，从源点流出的总水量，一定等于流入汇点的总水量，所以最大流可以定义为源点出流量的最大值。

怎么找最大流？一个朴素想法是：在管网里找一条还能“挤水”的路线。一条从 $s$ 到 $t$ 的路线只要每条管道都还有剩余空间，就可以往上加水量。能加多少，取决于这条路线上最细的那根管道，这个“最细处”叫瓶颈。我们把这样的路线称为增广路径，它的瓶颈容量是：

最大流问题像在问“全城供水极限”，而增广路径像一条条还能加水的备用管线路。算法要做的事，就是反复找出这些备用路线，直到整张管网彻底“挤不出”更多水为止。

Ford-Fulkerson 方法

水管工有个朴素的笨办法：只要还能找到一条从水库到城市、且每段都有余量的路，就把这条路线的瓶颈水量灌进去，然后重新看管网。这个反复“找路、灌水”的过程，就是 Ford-Fulkerson 方法的核心思想。它的关键在于，每次灌完水后不能只看原管道，还要看“剩余网络”。

为什么需要残余网络？因为水流进管道后，之前的选择可能不是最优的。为了允许“后悔”，我们要在残余网络中给每条已用管道加一条反向边，反向边的容量等于已经灌进去的水量。这样，如果后来发现某条路更优，就可以沿反向边把之前的水退回来，再绕到更好的路线上。残余容量定义为：

每找到一条增广路径 $P$，就沿着它更新路径上所有边的流量，增量就是瓶颈容量 $c_f(P)$。Ford-Fulkerson 的复杂度是 $O(E |f^*|)$，其中 $|f^*|$ 是最大流的值。如果最大流很大或容量是奇怪的数字，它可能跑得非常慢，甚至不终止。水管工很快意识到：不能乱找路线，得讲究策略。

最短增广路（Edmonds-Karp）

水管工决定每次只走“跳数最少”的备用路线，也就是从水库到城市经过的管道条数最少。这个策略就是 Edmonds-Karp 算法：每次用 BFS 在残余网络中找最短增广路，然后增广。BFS 像一层一层向外扩散的波纹，先碰到城市的路线一定是最短的。

为什么“每次选最短”能带来质变？因为 BFS 保证每条边不会被无限次地增广。可以证明，一条边最多被增广 $O(V)$ 次，整体最多有 $O(VE)$ 轮增广；每一轮 BFS 要扫描所有边，所以总复杂度是：

Edmonds-Karp 是可靠的水管工：它不追求一次灌很多，而是每次都挑最近的一条水路，虽然慢一点，但绝不会失控。不过对大型管网来说，一次只走一条路还是太保守了，我们还需要能“批量送货”的算法。

Dinic 算法

更聪明的调度员想：与其一趟一趟送，不如先画一张“分层地图”。所谓分层，就是用 BFS 算出每个中转站离水库的最小跳数，把管网分成第 0 层、第 1 层、第 2 层……只允许水从第 $k$ 层流向第 $k+1$ 层，不允许在同一层或倒退。这张分层图让调度变得井井有条。

在分层图上，调度员用一次 DFS 同时沿着多条可行路线灌水，直到再也找不到从 $s$ 到 $t$ 的合法路径，这时的流量称为阻塞流。一个分层阶段结束后，再重新 BFS 分层，重复下去。此外还有“当前弧优化”：已经用完的边不再重复尝试，相当于水管工在清单上把放空的水管划掉。每一阶段复杂度为 $O(VE)$，最多有 $O(V)$ 个阶段，所以：

如果把 Edmonds-Karp 比作每次只送一车水，Dinic 就是按楼层图一次性规划出整条水路网络，让多个车队同时出发。它保留了 BFS 的稳定，又借助分层和批量增广跑得更快，是竞赛和工程中的默认选手。

最大流最小割定理

现在我们来到整座供水网络的“军事机密”。假设入侵者想切断一些管道，让水库的水一滴也到不了城市。这组被切断的管道称为一个割：管道集合切掉后，所有节点被分成两堆——源点那一侧记为 $S$，汇点那一侧记为 $T$，割容量就是从 $S$ 侧流向 $T$ 侧的所有管道容量之和。入侵者当然希望用最小的破坏成本达成目的，这就是最小割。

为什么最大流恰好等于最小割？先看一个直观事实：任何从 $s$ 到 $t$ 的水流，都必须跨过 $S$ 和 $T$ 之间的“边界线”。所以任意流的大小都不会超过任意割的容量，即：

更进一步，在最大流对应的残余网络中，一定不存在增广路径。令 $S$ 为源点在残余网络中能到达的所有节点，那么从 $S$ 到 $T$ 的正向边全部满流、反向边流量为零，于是这个割的容量恰好等于当前流的值，流值达到上界。因此：

这个定理像一则寓言：防守方辛苦设计的最大运力，恰好等于进攻方最省力的破坏点。理解它，不仅得到理论美感，也得到实用的计算工具——想求最小割，直接跑一遍最大流算法，再根据最后一次 BFS 的可达集把割边找出来即可。

经典应用

最大流与最小割的“攻守平衡”在 AI 和计算机科学中遍地开花。第一个经典场景是二分图匹配：左边是一组员工，右边是一组任务，每个人只能做自己擅长的任务，问最多能安排多少个任务。把每个员工、每个任务变成节点，源点连员工，任务连汇点，匹配关系连容量为 1 的边，最大流就是最大匹配数。

第二个场景是项目选择：公司有一些项目，每个项目有正收益或负成本，项目之间还有依赖关系——选了某个项目就不得不选另一个。这种“最大权闭合子图”问题可以构造一个源点连正收益项目、负成本项目连汇点的网络，让最小割给出最优取舍：

第三个场景是图像分割：把像素看作节点，相邻像素的相似程度看成边的容量，通过最小割把图像切成前景和背景两块。这正是将图像里的“像素点分类”问题统一成了“切断最不相似区域”的图割问题。从水管到像素，最大流最小割这把刀始终锋利，因为它把“调度”和“切割”都翻译成了同一个数学语言。

AI 应用场景

Python 演示

from collections import deque class Dinic:    def __init__(self, n):        self.n = n        self.adj = [[] for _ in range(n)]     def add_edge(self, u, v, c):        # u 到 v 的正向边，容量为 c        self.adj[u].append([v, c, len(self.adj[v])])        # v 到 u 的反向边，容量为 0        self.adj[v].append([u, 0, len(self.adj[u]) - 1])     def bfs(self, s, t):        self.level = [-1] * self.n        q = deque([s])        self.level[s] = 0        while q:            u = q.popleft()            for e in self.adj[u]:                v, cap, rev = e                if cap > 0 and self.level[v] < 0:                    self.level[v] = self.level[u] + 1                    q.append(v)        return self.level[t] >= 0     def dfs(self, u, t, f):        if u == t:            return f        while self.it[u] < len(self.adj[u]):            e = self.adj[u][self.it[u]]            v, cap, rev = e            if cap > 0 and self.level[v] == self.level[u] + 1:                ret = self.dfs(v, t, min(f, cap))                if ret > 0:                    e[1] -= ret                    self.adj[v][rev][1] += ret                    return ret            self.it[u] += 1        return 0     def max_flow(self, s, t):        flow = 0        INF = 10 ** 9        while self.bfs(s, t):            self.it = [0] * self.n            while True:                f = self.dfs(s, t, INF)                if f == 0:                    break                flow += f        return flow # 与可视化动效一致的供水网络n = 4dinic = Dinic(n)dinic.add_edge(0, 1, 3)  # S -> Adinic.add_edge(0, 2, 2)  # S -> Bdinic.add_edge(1, 2, 1)  # A -> Bdinic.add_edge(1, 3, 2)  # A -> Tdinic.add_edge(2, 3, 2)  # B -> T print("max flow:", dinic.max_flow(0, 3))

1. self.adj[u].append([v, c, len(self.adj[v])])正向边记录目标节点、容量和反向边索引。
2. self.adj[v].append([u, 0, len(self.adj[u]) - 1])反向边初始容量为 0，专门用于“退流”。
3. if cap > 0 and self.level[v] < 0:BFS 只走还有剩余容量的边，给节点分层。
4. if cap > 0 and self.level[v] == self.level[u] + 1:DFS 严格沿层数加一的方向走，保证不绕圈。
5. e[1] -= ret正向边消耗掉本次增广的流量。
6. self.adj[v][rev][1] += ret反向边增加等量容量，允许之后后悔。
7. while self.bfs(s, t):只要还能分层成功，就进入新的增广阶段。
8. self.it = [0] * self.n每次阶段开始重置当前弧指针。

常见误区

面试题