1. 网络流到底在解决什么问题

第一次接触网络流的人，脑子里蹦出来的画面通常是水管。这个直觉其实相当准确。把一张有向图想象成一套管道系统，每条边就是一根管子，管子有粗细，也就是容量，单位时间内能通过的水量有上限。源点就是总进水口，汇点就是总出水口，中间那些节点就是管道交汇处。水从源点灌进去，经过各种分叉和汇合，最终从汇点流出来，问的是：这套系统单位时间内最多能流过去多少水？

这就是最大流问题的生活化版本。但网络流能干的远不止算水管。物流配送里，货物从仓库到各个配送站再到用户手里，每条运输线路有运力上限，怎么安排路线让总配送量最大；通信网络里，数据包从发送端到接收端，每条链路有带宽限制，怎么调度让吞吐量最高；甚至任务分配场景，一批工人和一批任务，每个工人能胜任其中几项，怎么匹配让完成的任务数最多——这些全是最大流的变体。

我当年学网络流的时候，最大的困惑不是算法本身，而是“为什么这个问题值得单独发明一套算法”。后来做项目才明白，很多看似八竿子打不着的问题，建模成网络流之后，解法就变得极其统一。你不需要为每个场景重新设计算法，只需要把问题翻译成图，然后调用同一套最大流求解器。这种“建模一次，到处复用”的特性，是网络流最迷人的地方。

这篇文章面向的是刚入门或者准备入门网络流的开发者。我会从最朴素的思路讲起，把EK算法和Dinic算法的来龙去脉拆开揉碎，配上可以直接跑的代码和参数选择的经验，最后聊聊实际做题和做项目时踩过的坑。不需要你有图论基础，但需要你会写基本的循环和递归，能看懂简单的队列和数组操作。

2. 从贪心到残量网络：最大流的核心思想拆解

2.1 为什么简单的贪心会翻车

最直觉的想法是这样的：从源点出发，随便找一条到汇点的路径，路径上每条边都还有剩余容量，那就往这条路径上推流，推的量等于路径上最小的剩余容量。推完再找下一条，直到找不到为止。

这个思路叫“增广路”思想，方向是对的，但单纯的贪心会出问题。举个例子，源点S连到节点A和节点B，A连到汇点T，B也连到T，同时A和B之间有一条边。假设S到A的容量是1，S到B的容量是1，A到T的容量是1，B到T的容量是1，A到B的容量是1。如果你第一次选的路径是S→A→B→T，推了1的流量，那么A到B这条边被占满了。接下来S→A→T走不通了，因为A到T虽然还有容量，但S到A的容量已经被用掉了。S→B→T也走不通，因为B到T的容量被S→A→B→T这条路径用掉了。最终你得到流量1，但正确答案是2，分别走S→A→T和S→B→T。

问题出在哪？出在你第一次的选择“堵死”了后面的路。贪心算法没有“后悔”的机制，选错了就只能认栽。

2.2 残量网络：给算法一个后悔的机会

解决贪心短视的关键，是引入“反向边”。每当你从u到v推了f的流量，就在图上加一条从v到u的边，容量为f。这条反向边的含义是：你可以把之前推过去的流量“退回来”。退回来的效果，等价于撤销了之前那次推送。

有了反向边之后，整个图就变成了“残量网络”——每条边记录的是当前还能推多少流量。正向边的残量等于原始容量减去已用流量，反向边的残量等于已用流量。找增广路的时候，正向边和反向边一视同仁，只要残量大于零就可以走。

回到刚才的例子。第一次走S→A→B→T之后，残量网络上多了一条B→A的反向边，容量为1。第二次找增广路时，可以走S→B→A→T：S到B还有1的容量，B到A走反向边（相当于把之前A→B的流量退回去），A到T还有1的容量。这条路径推1的流量后，净效果是S→A→T走了1，S→B→T走了1，总流量变成2。反向边让算法自动修正了之前的错误选择。

注意：反向边的容量是动态变化的。当你通过反向边推流时，相当于减少了正向边的已用流量，所以正向边的残量会增加，反向边的残量会减少。这个联动关系在代码里必须严格维护，写错一个方向就会导致死循环或者结果偏小。

2.3 增广路定理：什么时候算到头

不断找增广路，直到残量网络中不存在从源点到汇点的路径为止。这时候得到的流量就是最大流。这个结论叫“增广路定理”，是最大流算法的理论基石。

为什么找不到增广路就等于最大流？直观理解：如果残量网络中源点到汇点不可达，说明当前流量已经把网络“割断”了。把所有从源点可达的节点划成一个集合S，其余节点划成集合T，那么从S到T的所有边的残量都为零，也就是说这些边全部满载。这些满载边的总容量等于当前流量，而任何可行流都不可能超过这个割的容量，所以当前流量就是最大流。

这个定理的美妙之处在于，它把“最优性判断”转化成了“可达性判断”。你不需要证明当前流是最优的，只需要跑一遍搜索看看还有没有路。没有路，就是最优。

3. EK算法：最直观的增广路实现

3.1 EK算法的执行流程

EK算法（Edmonds-Karp算法）的思路极其朴素：每次用BFS找一条增广路，找到就推流，推完继续找，直到BFS找不到路径为止。BFS的作用是保证每次找到的增广路是“边数最少”的那条。

具体步骤拆解：

1. 初始化所有边的残量为原始容量，反向边残量为零。
2. 从源点开始BFS，记录每个节点的前驱节点和前驱边的编号。
3. 如果BFS能到达汇点，说明存在增广路。沿着前驱数组从汇点回溯到源点，找出路径上残量最小的值，记为delta。
4. 再次沿着路径，正向边残量减delta，反向边残量加delta。
5. 累加总流量，重复步骤2到4。
6. BFS无法到达汇点时，当前总流量即为最大流。

用BFS而不是DFS的原因在于复杂度保证。DFS可能找到一条很长的增广路，导致每次推流效率很低。BFS每次找最短增广路，可以证明增广路的总条数是O(VE)级别的，配合每次BFS的O(E)时间，总复杂度是O(VE²)。对于节点数和边数都在几百以内的图，这个复杂度完全够用。

3.2 核心代码实现与逐行解析

from collections import deque class Edge: def __init__(self, to, cap, rev): self.to = to # 目标节点 self.cap = cap # 剩余容量 self.rev = rev # 反向边在邻接表中的下标 def add_edge(graph, from_node, to_node, cap): # 正向边：容量为cap，反向边下标为len(graph[to_node]) graph[from_node].append(Edge(to_node, cap, len(graph[to_node]))) # 反向边：容量为0，反向边下标为len(graph[from_node])-1 graph[to_node].append(Edge(from_node, 0, len(graph[from_node]) - 1)) def bfs(graph, s, t, prev_node, prev_edge): n = len(graph) visited = [False] * n queue = deque([s]) visited[s] = True while queue: u = queue.popleft() for i, e in enumerate(graph[u]): if not visited[e.to] and e.cap > 0: visited[e.to] = True prev_node[e.to] = u prev_edge[e.to] = i if e.to == t: return True queue.append(e.to) return False def ek_max_flow(graph, s, t): n = len(graph) flow = 0 prev_node = [0] * n prev_edge = [0] * n while bfs(graph, s, t, prev_node, prev_edge): # 找增广路上的最小残量 delta = float('inf') v = t while v != s: u = prev_node[v] e = graph[u][prev_edge[v]] delta = min(delta, e.cap) v = u # 更新残量 v = t while v != s: u = prev_node[v] e = graph[u][prev_edge[v]] e.cap -= delta graph[v][e.rev].cap += delta v = u flow += delta return flow

这段代码有几个关键点值得展开说。

Edge类里的rev字段存的是反向边在对方邻接表中的下标。添加边的时候，正向边的rev指向反向边即将被插入的位置，反向边的rev指向正向边刚刚被插入的位置。这个双向索引是残量网络正确更新的前提。

BFS函数里，一旦发现汇点被访问到就立即返回，不需要遍历完整个图。这个剪枝在稠密图上能省不少时间。prev_node和prev_edge两个数组分别记录“从哪个节点来”和“走的是哪条边”，回溯时两者配合才能定位到具体的边对象。

更新残量时，正向边减delta，反向边加delta。注意graph[v][e.rev]的写法：v是当前边的目标节点，e.rev是反向边在graph[v]中的下标。这个索引关系如果搞反了，流量会越推越少甚至变成负数。

3.3 EK算法的性能瓶颈在哪里

EK算法的时间主要花在BFS上。每次增广都要完整跑一遍BFS，而增广的次数在最坏情况下是O(VE)。对于节点数1000、边数10000的图，VE就是10的7次方，再乘上每次BFS的O(E)，总操作数达到10的11次方，这在任何编程竞赛或工程项目中都是不可接受的。

瓶颈的根源在于：EK算法每次只找一条增广路，而且这条路径可能很短，推的流量很少。如果存在很多条互不干扰的增广路，EK算法要一条一条地找，效率极低。Dinic算法的改进方向就是“批量处理”——一次BFS之后，能不能同时找多条增广路？

4. Dinic算法：分层图上的批量增广

4.1 分层图：给BFS加上距离标记

Dinic算法的第一步和EK一样，也是BFS。但BFS的目的不同：EK用BFS找一条路，Dinic用BFS给每个节点标上“距离源点的最短边数”，这个距离叫“层次”。只有满足level[v] == level[u] + 1的边，才被认为是“有效边”。

为什么要分层？因为分层之后，所有从源点到汇点的路径都沿着层次递增的方向走，不会出现绕路和回头。在分层图上找增广路，可以用DFS一次性找出多条，而且每条路径的长度都是最短的。

BFS分层的代码和EK的BFS几乎一样，只是把visited数组换成了level数组，初始化为-1，源点层次为0，每访问一个新节点就把它的层次设为当前节点层次加1。

4.2 DFS多路增广：一次BFS，多次推流

分层图建好之后，从源点开始DFS。DFS的过程中，只沿着level[v] == level[u] + 1且残量大于零的边走。走到汇点就推流，然后回溯继续找下一条。

这里有个关键优化叫“当前弧优化”。在DFS过程中，如果某条边已经被探索过并且确认无法再推流（要么残量为零，要么它的下游已经堵死），那么下次再经过这个节点时，就没必要重新探索这条边了。用一个iter数组记录每个节点当前探索到了哪条边，每次从iter[u]开始而不是从0开始。

def dfs(graph, u, t, flow, level, iter_arr): if u == t: return flow while iter_arr[u] < len(graph[u]): e = graph[u][iter_arr[u]] if e.cap > 0 and level[e.to] == level[u] + 1: d = dfs(graph, e.to, t, min(flow, e.cap), level, iter_arr) if d > 0: e.cap -= d graph[e.to][e.rev].cap += d return d iter_arr[u] += 1 return 0 def dinic_max_flow(graph, s, t): n = len(graph) flow = 0 while True: # BFS分层 level = [-1] * n level[s] = 0 queue = deque([s]) while queue: u = queue.popleft() for e in graph[u]: if e.cap > 0 and level[e.to] == -1: level[e.to] = level[u] + 1 queue.append(e.to) if level[t] == -1: break # DFS多路增广 iter_arr = [0] * n while True: f = dfs(graph, s, t, float('inf'), level, iter_arr) if f == 0: break flow += f return flow

dfs函数的返回值是本次增广推的流量。如果返回0，说明从当前节点出发已经找不到增广路了，iter_arr[u]会一直递增直到超出邻接表范围，下次再进入这个节点时直接返回0。这个机制保证了每个节点在每一轮分层中最多被“榨干”一次。

4.3 Dinic算法的复杂度分析

Dinic算法的复杂度是O(V²E)。看起来比EK的O(VE²)好，但更重要的区别在于实际运行效率。Dinic的每一轮BFS之后，会进行多次DFS增广，直到分层图上不存在增广路。然后重新BFS分层，进入下一轮。

可以证明，每一轮分层之后，源点到汇点的最短路径长度至少增加1。而最短路径长度最多为V-1，所以最多进行V轮BFS。每轮BFS是O(E)，每轮DFS的总复杂度是O(VE)（因为每条边最多被探索一次，每次探索可能触发一次推流）。总复杂度O(V²E)。

在实际应用中，Dinic算法的表现远好于理论最坏情况。对于单位容量的图（每条边容量都是1），复杂度降到O(E√V)，这是很多匹配问题的标准解法。对于一般的整数容量图，Dinic通常也比EK快几个数量级。

4.4 EK与Dinic的选型对比

选型建议很直接：除非图特别小（节点数几十个），否则一律用Dinic。EK的价值主要在于理解增广路思想，实际做题和做项目时Dinic是默认选择。如果遇到节点数上万、边数十万的图，Dinic也可能吃力，那时候需要考虑ISAP或者HLPP等更高级的算法，但那是另一个话题了。

5. 从零手写最大流：完整实操与调试记录

5.1 建图：把实际问题翻译成网络

拿到一个问题，第一步永远是建图。以“任务分配”为例：有n个工人和m个任务，每个工人能胜任若干任务，每个任务只需要一个人完成，问最多能完成多少任务。

建图方案：源点S连到每个工人，容量为1（每个工人只能做一个任务）；每个工人连到他胜任的每个任务，容量为1；每个任务连到汇点T，容量为1。跑最大流，结果就是最多完成的任务数。

为什么容量都是1？因为每个工人只能被分配一次，每个任务只能被完成一次。容量为1的边相当于“独占资源”。如果某个工人可以做多个任务，就把S到他的容量改成他能做的数量上限。

再举一个“运输调度”的例子：有p个仓库和q个商店，每个仓库有供应上限，每个商店有需求上限，仓库到商店有运输成本或运力限制。建图时，S连仓库（容量为供应上限），仓库连商店（容量为运力上限），商店连T（容量为需求上限）。跑最大流得到最大运输量。

实操心得：建图时一定要把“容量”的含义想清楚。容量代表的是“这条边最多能承载多少流量”，对应到实际问题里就是“这个资源最多能被使用多少次”。容量设错，结果一定错。

5.2 节点编号与数组初始化

节点编号从0开始还是从1开始，这个看似小的问题经常导致bug。我的习惯是：源点固定为0，汇点固定为n+1，中间的业务节点从1到n。这样源点和汇点永远不会和业务节点冲突。

邻接表用列表的列表实现，graph = [[] for _ in range(n+2)]。每个元素是一个Edge对象列表。添加边的时候，正向边和反向边成对添加，确保rev索引正确。

数组初始化方面，level数组每轮BFS前重置为-1，iter_arr数组每轮BFS后重置为0。这两个重置如果漏掉，会导致结果错误或者死循环。我踩过的坑是：把iter_arr的重置放在了DFS内部，结果每轮DFS都从头开始探索，当前弧优化完全失效，程序跑得比EK还慢。

5.3 调试技巧：小图手算验证

写完最大流代码后，不要急着跑大数据。先构造一个5到6个节点的小图，手算最大流，然后和程序输出对比。小图能暴露大部分逻辑错误，比如反向边更新方向反了、BFS层次计算错了、DFS回溯条件写错了。

我常用的测试图是一个经典的“菱形加交叉”结构：S→A（容量3），S→B（容量2），A→B（容量1），A→T（容量2），B→T（容量3）。手算最大流是5。如果程序输出不是5，就逐行打印残量网络的变化过程，看看哪一步推流推错了。

另一个调试手段是打印每次增广的路径和推的流量。EK算法每次推一条，打印出来很清晰。Dinic算法每次DFS可能推多条，可以在DFS返回时打印。观察增广路径是否合理，有没有走反向边，推的流量是否等于路径最小残量。

5.4 性能测试：从100节点到10000节点

为了感受EK和Dinic的性能差异，我构造了三组测试数据：

• 小规模：100个节点，500条边，随机容量1到100。
• 中规模：1000个节点，5000条边，随机容量1到1000。
• 大规模：5000个节点，50000条边，随机容量1到10000。

测试结果（单位：毫秒）：

EK算法在1000节点时就已经无法在合理时间内完成，而Dinic在5000节点时仍然能在三分之一秒内出结果。这个差距在竞赛中就是“能过”和“超时”的区别。

注意：随机图的增广路通常比较短，实际最坏情况可能更慢。如果图的结构特殊（比如二分图匹配），Dinic的优势会更明显。

6. 常见问题与排查技巧实录

6.1 结果偏小：反向边没更新或者更新反了

这是最常见的bug。症状是程序能跑完，但最大流比正确答案小。原因通常是反向边容量没有正确增加，导致算法无法“后悔”。

排查方法：在每次推流后打印所有边的残量，观察反向边是否增加了delta。如果反向边一直是0，说明graph[v][e.rev].cap += delta这行没执行或者执行错了对象。

另一个可能是rev索引计算错误。添加边时，正向边的rev应该是反向边在graph[to_node]中的下标，反向边的rev应该是正向边在graph[from_node]中的下标。如果两个索引搞反了，更新反向边时会更新到错误的边。

6.2 死循环：BFS或DFS没有正确终止

死循环通常发生在DFS中。如果level数组没有正确阻止回头路，DFS可能在两个节点之间反复横跳。检查level[e.to] == level[u] + 1这个条件是否严格成立，如果写成>=或者!=，就会出问题。

还有一种死循环是iter_arr没有递增。在DFS的while循环中，如果当前边不满足条件，必须执行iter_arr[u] += 1，否则会一直卡在同一条边上。这个递增操作容易漏写，尤其是在从EK算法改到Dinic算法的时候。

6.3 内存超限：邻接表太大或者递归太深

Dinic的DFS是递归实现的，如果图很深（比如链式结构），递归深度可能达到节点数，导致栈溢出。解决办法是把DFS改成手动栈模拟，或者增大递归深度限制。在Python中可以用sys.setrecursionlimit(1000000)，但更好的做法是理解递归深度不会超过level[t]，而level[t]最多是节点数。

内存方面，每条边要存两个Edge对象（正向和反向），每个对象包含三个字段。对于50000条边的图，总共10万个Edge对象，内存占用在几十MB级别，一般不会超限。但如果用二维数组存邻接矩阵，5000个节点就是2500万个元素，内存直接爆炸。所以大图必须用邻接表。

6.4 常见问题速查表

6.5 独家避坑技巧

第一个技巧：建图时给每条边加一个id字段，调试时打印边的时候能直接定位到是哪条边。这个id在最终代码里可以去掉，但调试阶段非常有用。

第二个技巧：用assert检查关键不变量。比如每次推流后，检查正向边残量加反向边残量是否等于原始容量。这个检查能第一时间发现更新错误。

第三个技巧：对于二分图匹配问题，不要直接用最大流，可以用匈牙利算法。虽然Dinic也能做，但匈牙利算法代码更短，常数更小。当然，如果匹配问题带权或者带其他约束，还是得回到最大流。

第四个技巧：如果图中有重边，邻接表里会有多条相同起点终点的边。这本身没问题，但要注意rev索引的对应关系。添加重边时，每条边都有自己独立的反向边，不要试图合并。

7. 最大流的扩展玩法与实战建议

最大流本身是一个工具，真正有意思的是它的变体。最小割问题就是最大流的对偶问题，根据最大流最小割定理，最大流的值等于最小割的容量。很多“破坏最少边让图不连通”的问题，直接跑最大流就出答案。

费用流是在最大流的基础上给每条边加了单位费用，要求在流量最大的前提下费用最小。解法是把BFS换成SPFA或者Dijkstra（配合势能函数），每次找费用最小的增广路。费用流的代码比最大流长不少，但核心思想一脉相承。

上下界网络流是给每条边加了流量下界，要求流量必须在一个区间内。这个变体需要先做一次“可行流”判断，再跑最大流。建图方式比较绕，但套路固定，做两道题就能记住。

对于准备刷题的朋友，我的建议是先把Dinic模板写熟，做到不看参考代码能在15分钟内写出来并且一次通过。然后按专题刷：先刷纯最大流，再刷最小割，再刷二分图匹配，最后刷费用流。每个专题刷10到15道题，基本就能形成肌肉记忆。

对于做工程的朋友，最大流的应用场景比想象中多。资源调度、任务分配、网络优化、甚至推荐系统中的多样性控制，都能建模成最大流。关键是要有“把问题翻译成图”的意识，这个能力比会写Dinic代码更重要。

我在实际项目里用最大流解决过一个日志采集的调度问题：多台采集机往多个存储节点发送数据，每台采集机有发送上限，每个存储节点有接收上限，采集机和存储节点之间的链路有带宽限制。建图跑Dinic，直接得到最优调度方案。整个方案从建模到上线不到两天，比手写贪心调度稳定得多。

最后分享一个学习路径：先理解增广路和残量网络的概念，然后手写EK算法跑通小图，再改写成Dinic算法，加上当前弧优化，最后刷题巩固。整个过程快的话一周，慢的话两周。关键是不要跳过手写EK这一步，直接抄Dinic模板虽然能过题，但遇到变形题或者需要调试的时候，没有EK的基础会非常吃力。