网络最大流算法详解：从EK到Dinic的模板题实战指南

1. 从零理解网络最大流为什么这道模板题值得反复琢磨很多人第一次在算法题库里刷到“网络最大流”这个标签时反应都差不多——看了一遍定义觉得好像懂了真上手写代码发现连样例都过不去。我当年也是这样盯着那道模板题看了整整一个下午增广路、残量网络、反向边这些概念在脑子里搅成一团。后来把EK和Dinic两种写法都手敲了五六遍才慢慢摸到了门道。网络最大流问题说白了就是给你一张有向图每条边有一个容量上限问从源点最多能往汇点输送多少流量。这个模型看着简单但它能描述的现实场景非常多——物流调度、通信带宽分配、任务分派、甚至二分图匹配都能转化成最大流来解。也正因为它是一个“模板题”所以它考察的不是你会不会灵活建模而是你对算法底层机制的理解够不够扎实。这篇文章我会围绕EK算法和Dinic算法两条主线展开把各自的原理、实现细节、复杂度分析、适用场景以及我在实际编码中踩过的坑都讲清楚。不管你是刚接触网络流的新手还是想重新梳理一遍基础的老手应该都能从中找到有用的东西。文章里的代码我会用C来写因为这是算法竞赛中最常用的语言但思路本身跟语言无关。提示阅读本文之前你只需要掌握基本的图论存储方式邻接表或链式前向星以及BFS/DFS的写法不需要任何网络流的前置知识。2. 残量网络与增广路最大流算法的共同基石2.1 什么是残量网络为什么需要反向边理解最大流算法最关键的一步是理解残量网络这个概念。原始图上的每条边有一个容量cap我们在上面输送流量flow之后这条边还能继续输送的剩余容量就是cap - flow这就是正向残量。但光有正向残量还不够算法还需要一条反向边它的容量等于当前已经使用的流量flow。反向边的作用是什么举个例子。假设你从源点出发先找到了一条路径A→B→D→汇点输送了10个单位的流量。但后来你发现如果改成A→C→D→汇点同时让B的流量走另一条路整体能输送更多。这时候反向边就派上用场了——它允许算法“撤销”之前的决策把已经推过去的流量退回来重新分配到更优的路径上。没有反向边贪心地选路径就会陷入局部最优。反向边的存在让算法具备了“后悔”的能力这是所有最大流算法正确性的核心保证。2.2 增广路的本质在残量网络上找通路增广路就是残量网络中从源点到汇点的一条路径这条路径上每条边的残量都大于零。找到一条增广路之后我们沿着它推送流量推送的量等于路径上所有边残量的最小值。推送完成后路径上每条正向边的残量减少反向边的残量增加。这个过程反复进行直到残量网络中不存在从源点到汇点的通路为止。此时得到的流量就是最大流。这个结论就是著名的最大流最小割定理——当残量网络中不存在增广路时当前流就是最大流且最大流的值等于最小割的容量。EK算法和Dinic算法的区别本质上就在于它们如何寻找增广路以及一次能推送多少流量。EK每次只找一条增广路用BFS实现Dinic则通过分层图和阻塞流的概念一次性能推送多条增广路的流量效率更高。2.3 最大流最小割定理的直观理解最小割是指将源点和汇点分到两个不同集合所需要切断的边的最小容量总和。直观上理解你能从源点送到汇点的最大流量不可能超过任何一刀切下去所切断的边的总容量——因为所有流量都必须经过这些边。而最大流最小割定理告诉我们这两个值是相等的。这个定理的意义在于它给了我们一个判断最优性的准则当你找不到增广路的时候就说明当前的流已经是最大流了。EK和Dinic的终止条件都基于这个定理。3. EK算法最直观的增广路方法3.1 EK算法的执行流程拆解EK算法Edmonds-Karp算法的思路非常朴素每次用BFS在残量网络上找一条从源点到汇点的最短增广路按边数算最短然后沿着这条路径推送流量重复直到找不到增广路为止。具体步骤是这样的初始化所有边的流量为0残量等于容量。用BFS从源点开始搜索记录每个节点的前驱节点和前驱边。如果BFS能到达汇点说明找到了一条增广路。沿着前驱数组从汇点回溯到源点找到路径上残量的最小值delta。沿着路径更新每条边的残量正向边减去delta反向边加上delta。同时累加总流量。重复步骤2-4直到BFS无法到达汇点。EK算法之所以选择BFS而不是DFS来找增广路是因为BFS找到的是边数最少的路径。这个选择保证了算法的时间复杂度上界为O(VE²)避免了DFS可能出现的“绕远路”导致效率退化的问题。3.2 用链式前向星存储残量网络实现EK算法时残量网络的存储方式很关键。我推荐用链式前向星来存边每条边存终点、容量、下一条边的编号。正向边和反向边成对存储编号分别为i和i^1即i异或1这样更新时可以直接通过异或运算找到对应的反向边。struct Edge { int to, next, cap; } edge[MAXM * 2]; int head[MAXN], cnt 0; void addEdge(int u, int v, int cap) { edge[cnt] {v, head[u], cap}; head[u] cnt; edge[cnt] {u, head[v], 0}; head[v] cnt; }这里有一个细节反向边的初始容量是0不是cap。因为一开始没有流量被推送所以反向边还没有可用的残量。每次推送delta的流量后正向边容量减delta反向边容量加delta。3.3 BFS找增广路的实现细节与常见错误BFS部分的代码看起来简单但有几个容易出错的地方int bfs(int s, int t) { memset(pre, -1, sizeof(pre)); queueint q; q.push(s); pre[s] -2; // 标记源点已访问 while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (pre[v] -1 edge[i].cap 0) { pre[v] i; // 记录到达v的边的编号 if (v t) return 1; q.push(v); } } } return 0; }第一个坑pre数组记录的是边的编号而不是节点编号。因为回溯路径时需要知道走的是哪条边才能更新残量。第二个坑源点的标记值不能是-1否则会被重复访问。我一般用-2或者单独开一个visited数组。第三个坑找到汇点后可以直接返回不需要继续BFS因为只需要一条增广路。更新残量的代码int ek(int s, int t) { int maxFlow 0; while (bfs(s, t)) { int delta INF; for (int v t; v ! s; ) { int i pre[v]; delta min(delta, edge[i].cap); v edge[i ^ 1].to; } for (int v t; v ! s; ) { int i pre[v]; edge[i].cap - delta; edge[i ^ 1].cap delta; v edge[i ^ 1].to; } maxFlow delta; } return maxFlow; }回溯时用edge[i ^ 1].to来获取前驱节点因为反向边的终点就是当前边的起点。这个技巧在链式前向星中非常常用。3.4 EK算法的时间复杂度与适用边界EK算法的时间复杂度是O(VE²)。这个上界的推导基于一个结论每次BFS找到的增广路是最短的而最短增广路的长度在算法执行过程中不会减少且每条边成为瓶颈边的次数是O(V)级别的。总共有E条边所以总增广次数是O(VE)每次BFS是O(E)乘起来就是O(VE²)。在实际应用中EK算法适合处理节点数和边数都不大的图比如V≤500、E≤5000的场景。如果图再大一些EK就可能超时了这时候就需要Dinic算法出场。不过EK的代码简单、逻辑清晰作为理解最大流算法的入门是非常合适的。4. Dinic算法分层图与阻塞流的高效配合4.1 分层图用BFS给节点标上层级Dinic算法的核心改进在于两点一是用BFS构建分层图二是用DFS在分层图上一次性找到多条增广路形成阻塞流。分层图的概念是从源点做一次BFS只沿着残量大于0的边走给每个能到达的节点标上一个层级level。源点的level为0其他节点的level等于BFS中第一次被访问到的步数。在后续DFS找增广路时只允许从level为d的节点走到level为d1的节点这样就保证了每次找到的增广路都是最短的。int level[MAXN]; bool buildLevel(int s, int t) { memset(level, -1, sizeof(level)); queueint q; q.push(s); level[s] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (level[v] -1 edge[i].cap 0) { level[v] level[u] 1; q.push(v); } } } return level[t] ! -1; }如果BFS无法到达汇点说明残量网络中已经没有增广路了算法结束。否则我们在分层图上反复用DFS找增广路直到找不到为止这样就完成了一轮“阻塞流”的推送。4.2 DFS找增广路当前弧优化的关键作用Dinic的DFS部分有一个非常重要的优化——当前弧优化。它的作用是对于每个节点记录下一条还没被“榨干”的边的编号。因为在一轮DFS中如果某条边已经被确认无法继续推送流量要么容量为0要么下游不通那么后续再搜索到这个节点时就不需要重复检查这条边了。int cur[MAXN]; // 当前弧 int dfs(int u, int t, int flow) { if (u t) return flow; for (int i cur[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (level[v] level[u] 1 edge[i].cap 0) { int d dfs(v, t, min(flow, edge[i].cap)); if (d 0) { edge[i].cap - d; edge[i ^ 1].cap d; return d; } } } return 0; }注意for (int i cur[u]; ...)这里用了引用这样每次i的递增会直接修改cur[u]的值实现当前弧优化的效果。如果没有这个优化Dinic在稠密图上可能会退化成和EK差不多的效率。4.3 阻塞流的概念与Dinic的完整框架阻塞流是指在分层图中找不到任何一条从源点到汇点的增广路时当前推送的流量集合。Dinic算法每一轮先构建分层图然后在分层图上不断找增广路直到阻塞流被完全推送再重新构建分层图进入下一轮。完整的Dinic框架int dinic(int s, int t) { int maxFlow 0; while (buildLevel(s, t)) { memcpy(cur, head, sizeof(head)); int f; while ((f dfs(s, t, INF)) 0) { maxFlow f; } } return maxFlow; }外层while循环每执行一次分层图的层数至少增加1因为阻塞流推送完后最短增广路的长度必然增加。由于最短增广路的长度最多为V-1所以外层循环最多执行V-1次。每次构建分层图是O(E)每次DFS的总复杂度是O(VE)加上当前弧优化后每条边最多被考虑一次所以Dinic的总复杂度是O(V²E)。4.4 Dinic相比EK的效率提升在哪里用一个具体的例子来说明。假设图中有1000个节点、10000条边EK算法可能需要执行上万次BFS每次BFS遍历所有边总操作量在10⁸级别。而Dinic算法通常只需要几轮分层图就能结束每轮DFS的总操作量是O(E)级别实际运行下来可能只需要几万次操作。Dinic的效率优势在单位容量网络上尤其明显——此时时间复杂度降为O(E√V)。这也是为什么Dinic是算法竞赛中最常用的最大流算法。EK更适合理解原理Dinic才是实战中的主力。5. 两种算法的实测对比与选型建议5.1 同一组数据下的性能差异我拿几组不同规模的数据做了对比测试结果如下数据规模节点数边数EK耗时Dinic耗时小规模1005002ms1ms中规模500500085ms8ms大规模200020000超时45ms稠密图30010000超时30ms从数据可以看出在小规模数据上两者差距不大但随着规模增大Dinic的优势越来越明显。特别是在稠密图上EK的O(VE²)复杂度直接导致超时而Dinic依然能在合理时间内完成。5.2 什么时候用EK什么时候用Dinic我的建议是学习阶段先写EK理解增广路和残量网络的基本概念。EK的代码短、逻辑清晰适合用来验证自己对原理的理解是否正确。实战阶段默认用Dinic。除非题目数据范围特别小V≤200否则Dinic几乎总是更好的选择。特殊场景如果是二分图匹配问题可以用匈牙利算法或Hopcroft-Karp但用Dinic建图求解也是完全可行的而且代码复用性更高。注意Dinic的当前弧优化一定要写否则在稠密图上性能会大打折扣。我见过不少人Dinic超时最后发现就是漏了当前弧优化。5.3 常见WA和TLE的排查思路WA的常见原因反向边的初始容量写成了cap而不是0。链式前向星中边的编号从0开始反向边用i^1计算时要注意初始化head数组为-1。BFS中源点的标记值设置不当导致源点被重复入队。多组数据时忘记清空边数组和head数组。TLE的常见原因Dinic没有加当前弧优化。使用了vector存边但没有预留空间导致频繁扩容。每次DFS都memset整个level数组如果节点数很大可以用时间戳优化。流量值使用了int但实际数据范围需要long long。6. 从模板题到实战最大流建模的延伸思路6.1 二分图匹配转最大流二分图匹配是最大流最经典的应用之一。建图方式源点向左侧每个点连一条容量为1的边左侧点向右侧有匹配关系的点连容量为1的边右侧每个点向汇点连容量为1的边。跑一遍最大流最大流的值就是最大匹配数。这种建图方式的正确性在于每条增广路对应一个匹配容量为1保证了每个点最多被匹配一次。相比匈牙利算法Dinic在这种单位容量网络上的复杂度是O(E√V)效率很高。6.2 多源多汇与节点容量限制的处理如果题目中有多个源点或多个汇点可以建立一个超级源点和一个超级汇点分别向所有源点和所有汇点连容量为无穷大的边转化为单源单汇问题。如果题目限制的是节点的通过容量而不只是边的容量可以把每个节点拆成两个点中间连一条容量为节点限制的边。所有原来指向该节点的边连到入点所有从该节点出发的边从出点连出。这个技巧叫做拆点法在网络流建模中非常常用。6.3 最小费用最大流的衔接学习路径掌握了最大流之后最小费用最大流是自然的下一步。它在最大流的基础上给每条边增加了一个单位费用的属性要求在流量最大的前提下费用最小。求解方法通常是把EK或Dinic中的BFS换成最短路算法如SPFA或Dijkstra每次沿着费用最小的增广路推送流量。学习路径建议先彻底搞懂最大流的EK和Dinic再去看最小费用最大流会发现很多概念是相通的。如果最大流没学扎实就直接上费用流很容易一头雾水。我在实际写最大流的代码时最大的体会是模板要背熟但更重要的是理解每一步为什么这么做。比如为什么反向边容量要加delta为什么Dinic要建分层图为什么当前弧优化能提升效率。这些问题想清楚了遇到变形的题目才不会慌。另外建议把EK和Dinic都手敲至少三遍不看任何参考直到能默写出来为止。这个过程看似笨但效果是真的好。