1. 从零搞懂最大流为什么每个搞算法的人都绕不开这两个算法第一次接触网络流的人大概率会有两种反应一种是“这不就是水管灌水吗有什么难的”另一种是“这公式和证明也太劝退了”。我当初属于后者。直到某次做一个资源调度的小工具需要把一批任务分配给若干台机器每台机器有容量上限每个任务有归属限制我才真正意识到——最大流不是一道竞赛题它是很多实际问题的通用解法。这篇内容就是把我从“看不懂证明”到“能默写EK和Dinic”的整个过程拆开讲。核心关键词就三个网络流、EK算法、Dinic算法。我会先讲清楚最大流到底在解决什么问题再分别把EK和Dinic的实现思路、代码、复杂度、适用场景掰开揉碎最后给出一份可以直接抄的模板和一堆踩坑经验。适合刚学完图论基础、想入门网络流的同学也适合工作中遇到分配、匹配、调度类问题想找工具的人。不需要你会高深的数学证明只要能看懂BFS和DFS这篇就能带你上手。先说结论方便你建立预期EK算法好理解但慢Dinic算法稍复杂但快得多绝大多数场景直接上Dinic。但为什么还要学EK因为EK是理解“增广路”和“残量网络”这两个核心概念的最佳入口跳过它直接看Dinic你会觉得代码里那些反向边、分层图像是凭空冒出来的。所以我的建议是先吃透EK再升级到Dinic这条路最稳。2. 最大流问题到底在解决什么先建立正确的直觉模型2.1 用“水管网络”理解流、容量和最大流网络流的标准模型是这样的有一张有向图每条边有一个容量capacity表示这条边最多能通过多少流量有一个源点source通常记作S流量从这里出发有一个汇点sink通常记作T流量最终汇聚到这里。除了源点和汇点中间节点的流入量必须等于流出量这叫流量守恒。生活化的类比就是一套自来水管道系统S是水厂T是用户小区每条管道有粗细容量水从水厂流到小区中间的中转站只负责转发不能凭空产生水也不能囤水。最大流问题就是问从水厂到小区单位时间内最多能送多少水这里有个容易被忽略的点容量限制的是“单位时间通过量”不是总量。所以最大流求的是一个速率不是累计值。理解这一点后面看残量网络才不会迷糊。2.2 残量网络整个网络流算法的灵魂如果只记住一个概念那一定是残量网络residual network。它的定义是对于每条原边正向还能再推多少流量就有一条对应容量的正向残量边同时已经推过去的流量可以“反悔”退回来所以还有一条反向残量边容量等于当前已用流量。为什么要有反向边这是新手最容易卡住的地方。我举个具体例子假设你一开始给某条路径推了流量后来发现这条路径占用了本该给另一条更优路径的边如果没有反向边你就没法撤销这个错误决定。反向边的存在让算法具备了“后悔”的能力——把之前推的流量退回去改走别的路。没有反向边贪心就会走进死胡同有了反向边贪心才能收敛到全局最优。提示残量网络里正向边容量 原容量 - 已用流量反向边容量 已用流量。每次增广后这两者都要同步更新这是所有最大流算法的公共操作。2.3 增广路每次找一条还能推流量的路径增广路augmenting path指的是残量网络中从S到T的一条路径这条路径上每条边的残量都大于0。找到一条增广路后我们沿着它推流量推的量等于路径上最小的残量这叫瓶颈容量。推完之后更新残量网络继续找下一条增广路直到再也找不到为止。这里有个著名的定理最大流最小割定理当残量网络中不存在从S到T的增广路时当前的流就是最大流。这个定理是EK和Dinic正确性的基石也是为什么算法可以放心地在“找不到增广路”时停下来。理解了这三个概念——容量、残量网络、增广路——你就已经掌握了最大流80%的核心思想。剩下的EK和Dinic区别只在于“怎么找增广路”。3. EK算法最直观的增广路实现入门首选3.1 EK算法的核心思路BFS找最短增广路EK算法Edmonds-Karp的思路朴素到令人感动每次用BFS在残量网络里找一条从S到T的增广路找到就推流量推完继续找直到BFS找不到T为止。为什么用BFS而不是DFS因为BFS找到的是边数最少的增广路。这个选择不是随便定的它直接决定了EK的复杂度。用BFS保证每次增广的都是最短路径可以证明增广次数是O(VE)级别的配合每次BFS的O(E)总复杂度是O(VE²)。如果用DFS随便找最坏情况下可能陷入指数级的增广次数。所以BFS是EK的灵魂不是随便挑的搜索方式。3.2 EK的完整实现与逐行注释下面是一份可以直接用的EK模板我用链式前向星存图这是竞赛和工程里最常用的方式比邻接矩阵省空间比vector存边更紧凑。#include bits/stdc.h using namespace std; const int MAXN 10005; const int MAXM 200005; const long long INF 1e18; struct Edge { int to, next; long long cap; } edge[MAXM]; int head[MAXN], cnt 0; int pre[MAXN]; // 记录增广路上每个点的前驱边编号 long long flow[MAXN]; // 到每个点为止的瓶颈容量 void addEdge(int u, int v, long long cap) { edge[cnt] {v, head[u], cap}; head[u] cnt; edge[cnt] {u, head[v], 0}; // 反向边初始容量为0 head[v] cnt; } bool bfs(int s, int t, int n) { memset(pre, -1, sizeof(int) * (n 1)); queueint q; q.push(s); flow[s] INF; while (!q.empty()) { int u q.front(); q.pop(); if (u t) break; 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; flow[v] min(flow[u], edge[i].cap); q.push(v); } } } return pre[t] ! -1; } long long EK(int s, int t, int n) { long long maxFlow 0; while (bfs(s, t, n)) { long long add flow[t]; maxFlow add; int u t; while (u ! s) { int e pre[u]; edge[e].cap - add; // 正向边减 edge[e ^ 1].cap add; // 反向边加 u edge[e ^ 1].to; } } return maxFlow; }几个关键点解释一下。edge[e ^ 1]是反向边的技巧因为正向边和反向边是成对添加的编号只差1偶数正向、奇数反向所以用异或1就能互相找到。flow[v] min(flow[u], edge[i].cap)是在BFS过程中同步维护瓶颈容量这样找到T的时候直接就知道该推多少不用再回溯一遍。pre数组记录的是边的编号而不是点的编号这样回溯更新的时候能直接定位到边。3.3 EK的复杂度与适用边界EK的时间复杂度是O(VE²)。这个复杂度在稠密图上其实不算太差但在稀疏大图上会明显吃力。我实测过一个V2000、E10000的图EK跑了大概几秒而Dinic在毫秒级就出结果了。那EK还有用吗有。当图很小、或者你只是需要快速验证一个想法时EK的代码短、逻辑清晰调试成本极低。另外EK的增广次数上界O(VE)这个结论本身在理论分析里很有价值。我的建议是把EK当作理解网络流的教学工具和快速原型工具正式提交或上线时换成Dinic。注意EK里每次BFS都要重置pre数组重置范围是n1而不是MAXN否则在大规模数据下memset会成为隐藏的性能瓶颈。这个细节很多人不注意实测能差出不少时间。4. Dinic算法多路增广分层图性能的质变4.1 Dinic的两个核心优化分层图与当前弧Dinic相比EK做了两个关键优化直接把复杂度从O(VE²)降到了O(V²E)。第一个优化是分层图level graph。Dinic先用一次BFS给每个点标上到S的最短距离层数然后只允许沿着“层数1”的方向走。这样做的好处是一次BFS之后可以连续找多条增广路而不是像EK那样找一条就重新BFS。因为所有增广路都沿着层数递增的方向所以不会出现绕圈的情况。第二个优化是当前弧优化current arc。在DFS找增广路时用一个cur数组记录每个点已经尝试到了哪条边。因为一条边如果已经确认推不动流量了之后就不用再试它。这个优化避免了大量重复扫描是Dinic性能的关键。这两个优化叠加让Dinic在实际运行中通常远快于理论复杂度很多图上跑起来接近线性。4.2 Dinic的完整实现与关键细节#include bits/stdc.h using namespace std; const int MAXN 10005; const int MAXM 200005; const long long INF 1e18; struct Edge { int to, next; long long cap; } edge[MAXM]; int head[MAXN], cnt 0; int level[MAXN], cur[MAXN]; int n, m, s, t; void addEdge(int u, int v, long long cap) { edge[cnt] {v, head[u], cap}; head[u] cnt; edge[cnt] {u, head[v], 0}; head[v] cnt; } bool bfs() { memset(level, -1, sizeof(int) * (n 1)); 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; } long long dfs(int u, long long pushed) { if (u t) return pushed; 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) { long long tr dfs(v, min(pushed, edge[i].cap)); if (tr 0) { edge[i].cap - tr; edge[i ^ 1].cap tr; return tr; } } } return 0; } long long Dinic() { long long maxFlow 0; while (bfs()) { memcpy(cur, head, sizeof(int) * (n 1)); while (long long pushed dfs(s, INF)) { maxFlow pushed; } } return maxFlow; }重点看dfs里的for (int i cur[u]; ...)这个引用是关键。i是cur[u]的引用每次循环i自增实际上就是在更新cur[u]。这样当某条边被确认推不动后下次再访问这个点就直接从下一条边开始不会重复扫描。这个引用写法是当前弧优化的标准实现漏掉引用就退化成了普通DFS。另一个细节是dfs每次只返回一条增广路的流量外层用while循环反复调用。这种写法比一次性推多条更清晰也方便调试。如果追求极致性能可以改成一次DFS推多条多路增广但代码会复杂一些收益在多数场景下不明显。4.3 EK与Dinic的对比什么时候用哪个对比维度EK算法Dinic算法核心思路BFS找单条增广路BFS分层DFS多路增广时间复杂度O(VE²)O(V²E)代码复杂度低约50行中约70行小图表现够用够用大图表现明显偏慢快通常毫秒级调试难度低中分层和当前弧易出错推荐场景教学、原型验证正式提交、工程落地我的实际经验是只要图的规模超过V500或E2000就无脑上Dinic。EK在这个规模以上会开始出现肉眼可见的延迟而Dinic基本无感。但如果你是在面试白板上写代码EK更不容易写错可以先用EK讲清楚思路再口述Dinic的优化点。5. 从建图到出结果一份可复现的完整实操流程5.1 建图阶段把实际问题翻译成网络流模型网络流最难的部分从来不是算法本身而是建图。算法是固定的但怎么把实际问题抽象成点、边、容量才是真正考验功力的地方。以“任务分配”为例有若干任务要分配给若干机器每个任务只能给特定机器每台机器有处理数量上限。建图方式是源点S连每个任务容量为1每个任务做一次任务连它能做的机器容量为1机器连汇点T容量为机器上限。跑一遍最大流流量就是最多能完成的任务数。建图的核心套路是源点连“供给方”汇点连“需求方”中间连“约束关系”容量表示“限制条件”。大部分最大流问题都能套进这个框架。我踩过的坑是一开始总想把所有东西都塞进图里结果点边数量爆炸。后来学会先问自己——哪些是真正的约束哪些可以合并。能合并的节点一定要合并否则图会大得没必要。5.2 参数选择容量类型与INF的取值容量用int还是long long这取决于题目数据范围。如果单条边容量和总流量可能超过2×10⁹就必须用long long。我一般默认用long long因为网络流的加法很容易溢出用int省的那点空间不值得冒险。INF的取值也有讲究。它要大于“任何可能的瓶颈容量”通常取总流量上界。如果边数最多200000单边容量最大10⁹那总流量上界是2×10¹⁴INF取1e18就足够安全。千万不要取INT_MAX然后拿去和long long比较类型不匹配会出隐蔽的bug。5.3 实操现场一个完整例子的运行记录我用一个具体例子走一遍。图有4个点S1T4边如下1→2 容量 31→3 容量 22→3 容量 12→4 容量 23→4 容量 4用Dinic跑第一次BFS分层level[1]0, level[2]1, level[3]1, level[4]2。DFS从1出发走1→2→4瓶颈min(3,2)2推2更新残量。继续DFS1→3→4瓶颈min(2,4)2推2。此时从1出发的边都推完了第一轮结束maxFlow4。第二次BFS发现1→2还有残量1但2→4已经满了2→3有残量13→4还有残量2所以路径1→2→3→4瓶颈min(1,1,2)1推1。maxFlow5。第三次BFSlevel[t]-1结束。最终最大流是5。这个例子手算一遍比看十遍代码都管用。强烈建议你拿纸笔把残量网络的每次更新画出来画完你就彻底懂了。6. 常见问题与排查技巧实录6.1 结果偏小八成是反向边或残量更新出了问题最大流结果比预期小最常见的原因是反向边没建对或者更新时正反向搞反了。检查方法打印每次增广的路径和推的流量看是否出现了“本该能推但没推”的情况。另一个高频错误是addEdge里反向边初始容量写成了cap而不是0这会导致凭空多出流量。还有一种隐蔽情况BFS的终止条件写错。比如在EK里BFS找到T之后应该立即break但如果你继续把队列跑完flow[t]可能被后续路径覆盖成更小的值。这个bug很隐蔽因为小图上可能碰巧不出错。6.2 死循环当前弧没更新或层数判断写反Dinic跑不出结果、一直循环通常是两个原因。一是cur数组没在每轮BFS后重置导致上一轮的进度被带到下一轮逻辑就乱了。二是层数判断写成了level[v] level[u] - 1方向反了导致DFS一直在原地打转。层数判断必须是level[v] level[u] 1因为我们要沿着离S越来越远的方向走。6.3 性能问题memset范围和递归深度性能问题我遇到最多的是memset范围过大。每次BFS都memset(level, -1, sizeof(level))如果MAXN是100000而实际n只有1000就白白清了99000个位置。改成sizeof(int) * (n 1)能省不少时间。另一个是递归深度。Dinic的DFS是递归的如果图是一条长链递归深度可能达到VV很大时会栈溢出。解决办法是开大栈空间或者把DFS改成非递归。我一般先开栈实在不行再改迭代。问题现象可能原因排查方法结果偏小反向边容量错、残量更新反了打印增广路径和流量死循环cur未重置、层数判断反了检查level[v]level[u]1运行超时memset范围大、递归深缩小memset、改迭代答案溢出用了int存流量全改long long建图后无解源汇连接方向错检查S连供给、需求连T提示调试网络流最有效的手段是“小图手算打印中间状态”。不要一上来就在大图上调先构造一个5个点以内的小图把每次BFS的层数和每次DFS的路径打出来对照手算结果问题基本一眼就能看出来。7. 我踩过的坑和几条实用建议学网络流这段时间我踩的坑比想象中多。最开始我总觉得算法看懂了就行结果第一次自己写Dinic当前弧优化漏了引用跑大图直接超时查了半天才发现是int i cur[u]而不是int i cur[u]。这个引用加不加性能差好几倍但代码看起来几乎一样特别容易忽略。第二个坑是建图时点编号从0开始还是从1开始。我有一份代码混用了两种编号结果反向边异或操作全乱了。后来我强制自己统一从1开始编号源点固定为1汇点固定为n再也没出过这个问题。第三个建议是把EK和Dinic都背下来但理解优先于背诵。我见过有人能默写Dinic但说不清为什么要分层结果题目稍微一变建立模型就懵了。网络流的价值在于建模算法只是工具。多花时间在“怎么把问题变成图”上比死磕算法优化划算得多。最后分享一个我常用的验证技巧写完最大流代码后先用一个已知答案的小图跑一遍再用一个随机生成的小图把最大流结果和最小割的暴力枚举结果对比。两者相等就说明代码是对的。这个交叉验证方法帮我抓出过好几次隐蔽的bug比单纯看代码靠谱得多。