1. 从“死磕DFS”到“老老实实BFS”EK算法到底解决什么问题很多刚接触网络流的朋友第一次看最大流问题时都会觉得这有什么难的从源点使劲往汇点灌水灌不动了就是最大流呗。但真正动手实现就会发现问题没那么简单——你按什么路径灌灌满了之后怎么反悔为什么DFS瞎找路径可能找半天还结不了题我当年第一次自己实现最大流就是用朴素的DFS去找增广路从源点出发一路沿着还有剩余容量的边往汇点走找到一条就算一条所有路径流量加起来就是答案。这个思路本身是对的它叫Ford-Fulkerson方法但它只给出了一个框架没有规定具体怎么找增广路。如果DFS每次都走一条“绕远路”增广次数会非常多在最坏情况下甚至能慢到让人怀疑人生。EK算法做的事情说来很简单把DFS换成BFS每次在残留网络里找一条“边数最少”的增广路。这个改动看起来轻描淡写却把复杂度从“可能爆炸”拉到了O(V·E²)的多项式级别这就是它的核心价值。所谓残留网络是废弃当前流量图之后剩余可用的网络这个术语听着玄实际上就是每个节点之间的边还能不能再走、能走多少的问题。EK算法的每一步都是在残留网络里用BFS找一条从源点到汇点的最短路径然后在这条路径上做流量更新。这里有个很关键的直觉为什么一定要用BFS而不是DFS因为BFS找到的是边数最少的路径这保证了增广路径的“边数”是单调不降的。也就是说越到后面找出来的最短路径只会越来越长或者持平不会倒退。这个单调性是后续时间复杂度证明的基石。你可以把增广过程看成在和一个迷宫较劲——每次都走最短出口比瞎碰运气要高效得多。EK算法适合谁适合刚开始接触网络流的人它直观、好写、不容易出逻辑错代码量也很小。它也是理解Dinic算法的最佳跳板因为Dinic的本质就是“多路增广的EK”。甚至在很多数据范围不极端的题目里EK就已经能直接过题不需要一上来就上Dinic。有了这个认知基底下面我们正式把EK算法的机制拆开来看。2. 残留网络与反向边为什么最大流需要“后悔药”2.1 残留网络的定义与直观理解先定义清楚给定一个有向图G(V,E)每条边u→v有容量c(u,v)没有边则为0。如果当前已经在这条边上流了f(u,v)的流量那么正向还能再走的容量是 c(u,v) - f(u,v)这是“剩余容量”。反向的“虚拟容量”是 f(u,v)代表着我们可以把已经流过的流量“退回去”。残留网络就是由这些正向剩余容量和反向虚拟容量构成的一个新图。残留网络中每条边上的值叫残余容量。我用个日常场景来解释。想象你在一个小吃街的配送站向两个摊位送食材。第一条路往东走可以直接到A摊能送10斤。你派了6斤过去那么这条路还能再走4斤这是正向剩余。可你发现B摊更急而走到A摊的那6斤物资其实可以调头回来再改走另一条路这时那条骑过的路就产生了一条“回头路”允许配送员带着货物原路返回这就是反向边的作用。最大流算法里反向边干的就是这事——给之前的决策一个“撤回机会”。DFS那种贪心思路如果没有反向边经常会出现一开始占了某条路后面发现另一条路更优却无法调整的僵局。有了反向边流算法就可以通过“退流”重新规划路径最终达到全局最优。2.2 反向边的容量变化规则假设u→v的容量是10当前已经流了3。在残留网络中u到v的正向残余容量10 - 3 7。v到u的反向残余容量3。如果我们通过反向边把3的流量“退回去”相当于把当前流量调整成0那正向容量又恢复成10反向变成0。你发现没有这个机制的本质就是每次增广都能把之前画的流量图擦掉一部分重新再画直到所有的流量分配都没有更好的调整空间为止。这像一个桌游里翻牌后悔的规则允许你回退有限步但每一步回退都要消耗一次操作机会。最大流算法里的“操作机会”就是增广轮数BFS保证这个轮数可控。2.3 为什么找最短增广路能保证多项式复杂度每次用BFS找最短增广路其路径长度至少为1最多为V-1条边。EK算法的证明核心在于每条边成为“关键边”即增广后残余容量变为0导致被删掉的次数是O(V)级别的。因为每次某条边变为0后下次它要想再变成非零必须经过一次反向增广而反向增广又意味着最短路径长度至少增加了2。由于路径长度最多是V-1所以每条边最多被“删”O(V)次。残留网络里每轮BFS之后最短路径长度不会变短这个性质非常关键。我在初学的时候一直没搞懂“为什么路径长度不会变短是好事”其实反过来想如果路径长度会变短说明之前BFS找到的最短路径有漏洞算法可能会出现反复横跳的情况收敛性就很难证明。正是这个单调性保证了总的增广轮数是O(VE)每轮BFS的代价是O(E)于是整体是O(VE²)。2.4 一个手工模拟的极简例子考虑最简单的一张图源点S → A容量2S → B容量2A → T容量2B → T容量2A → B容量1如果一开始DFS运气不好走了S→A→B→T把A→B的容量堵死那么后续S→A就没法再往T送流了如果算法没有反悔机制结果算出来是1但正确答案其实是2S→A→T和S→B→T各走2。但EK不一样。第一轮BFS会找到S→A→T因为BFS优先考虑最短边数路径流2第二轮BFS找到S→B→T流2直接得到正确结果。即使某次BFS选了S→A→B→T反向边也会允许后续BFS把A→B上那1的流量退回去从而给S→A→T腾出空间。这正是反向边的意义。3. 邻接表实现细节结构体设计、BFS找增广路与流量回溯现在上最实在的部分用邻接表实现EK算法。为什么强调邻接表因为邻接矩阵在边很多、顶点多的情况下内存吃不消而且EK算法本身代码里需要灵活地在正反向边之间跳转邻接表配合“边索引成对”的技巧会非常顺手。3.1 结构体设计与边的存储方式我们用如下结构体存一条边struct Edge { int to; // 这条边指向的顶点 int cap; // 当前残余容量会随着增广动态改变 int rev; // 反向边在邻接表里的下标 };这里有个非常重要的技巧反向边的下标必须记录。我们插入正向边u→v时同时往graph[v]里插入反向边v→u然后把反向边在graph[v]里的下标记录在正向边的rev字段里。同理反向边的rev字段记录正向边在graph[u]里的下标。这种成对插入的好处是增广时如果想“退回”流量直接通过rev字段找到对方不需要额外维护映射关系。用邻接矩阵时你可能觉得rev字段多余毕竟矩阵是天然的对称结构但邻接表必须靠这个字段跳转。vectorEdge G[MAXN]; void addEdge(int from, int to, int cap) { G[from].push_back(Edge{to, cap, (int)G[to].size()}); G[to].push_back(Edge{from, 0, (int)G[from].size() - 1}); }注意第二行反向边的cap初始化为0。这代表一开始这条反向路径没有任何可退的流量只有当你往正向边流过流量之后反向残余容量才会增加。3.2 BFS找增广路pre数组的设计BFS需要记录两件事每个节点是从哪条边过来的、那个前驱节点是谁。这样才能在找到汇点后倒推出整条增广路径。这里我习惯用两个数组preV[i]表示走到节点i的前一个节点preE[i]表示前驱节点中对应边的编号在graph[preV[i]]中的下标。也就是preE[i]指向的那条Edge的to值恰好是i。bool bfs(int s, int t) { memset(preV, -1, sizeof(preV)); memset(preE, -1, sizeof(preE)); queueint q; q.push(s); preV[s] s; // 源点的前驱设为自己表示已访问 while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i (int)G[u].size(); i) { Edge e G[u][i]; if (e.cap 0 preV[e.to] -1) { preV[e.to] u; preE[e.to] i; if (e.to t) return true; // 找到汇点提前退出 q.push(e.to); } } } return false; }这里的两个判断条件缺一不可cap 0保证这条路还走得通preV[e.to] -1保证每个节点在一轮BFS中只被访问一次。另外preV[s] s这行容易被忽略。没有它源点可能被后续的边再次入队导致死循环或路径记录出错。3.3 增广与流量回溯BFS只要返回true就说明找到了一条从s到t的增广路。接下来我们要做两件事找到这条路能增广的“瓶颈值”——也就是路径上最小的残余容量。沿路径正向边扣减瓶颈值反向边增加瓶颈值。代码实现如下int maxFlow(int s, int t) { int flow 0; while (bfs(s, t)) { int d INF; // 从汇点往回找瓶颈值 for (int v t; v ! s; v preV[v]) { int u preV[v]; d min(d, G[u][preE[v]].cap); } // 更新残留网络 for (int v t; v ! s; v preV[v]) { int u preV[v]; Edge e G[u][preE[v]]; e.cap - d; G[v][e.rev].cap d; } flow d; } return flow; }注意第二个循环里修改e是引用操作不能写成Edge e G[u][preE[v]]否则对e.cap的修改不会写回原数组。这是新手非常容易踩的坑。增广完之后flow累加进入下一轮BFS。当BFS返回false说明源点到汇点已经不存在可增广路径此时flow就是最大流。3.4 一个完整可编译的邻接表EK模板给一个可以直接复制去尝试的最简完整模板顶点编号从0开始适用重边情况因为重边在邻接表里是两个独立元素各自参与BFS和增广天然支持#include bits/stdc.h using namespace std; const int MAXN 205; const int INF 0x3f3f3f3f; struct Edge { int to, cap, rev; }; vectorEdge G[MAXN]; int preV[MAXN], preE[MAXN]; void addEdge(int from, int to, int cap) { G[from].push_back(Edge{to, cap, (int)G[to].size()}); G[to].push_back(Edge{from, 0, (int)G[from].size() - 1}); } bool bfs(int s, int t) { memset(preV, -1, sizeof(preV)); memset(preE, -1, sizeof(preE)); queueint q; q.push(s); preV[s] s; while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i (int)G[u].size(); i) { Edge e G[u][i]; if (e.cap 0 preV[e.to] -1) { preV[e.to] u; preE[e.to] i; if (e.to t) return true; q.push(e.to); } } } return false; } int maxFlow(int s, int t) { int flow 0; while (bfs(s, t)) { int d INF; for (int v t; v ! s; v preV[v]) { d min(d, G[preV[v]][preE[v]].cap); } for (int v t; v ! s; v preV[v]) { Edge e G[preV[v]][preE[v]]; e.cap - d; G[v][e.rev].cap d; } flow d; } return flow; } int main() { int n, m; cin n m; int s, t; cin s t; for (int i 0; i m; i) { int u, v, c; cin u v c; addEdge(u, v, c); } cout maxFlow(s, t) endl; return 0; }这个模板在点数和边数均为1e3量级时跑起来非常舒服。如果边数到了1e5EK就不太行了得换Dinic。4. 实测中容易翻车的几个坑多组数据、零流量边与死循环排查写EK算法时大多数人的问题不是不理解原理而是死在实现细节上。这里我把自己调试过程中踩过的坑统一列一下每个都是血泪教训。4.1 多组测试数据时忘清空邻接表很多题目是多组输入每组都重新建图。如果你直接在原有G数组上继续addEdge上一组的边没清空新旧边混在一起BFS可能在旧边上找到“幽灵路径”导致流量计算错误。正确做法是在每组测试开始时把G数组每个元素clear一遍for (int i 0; i MAXN; i) G[i].clear();这段代码虽然简单却是我见过最多的WA原因之一。它不需要动脑筋但忘掉的代价非常大。4.2 零容量边入队导致逻辑混乱BFS里已经判断了e.cap 0所以零容量边理论上不会入队。但有一种情况要注意某条边的cap初始为0后来通过反向增广变成正数——这在EK算法中完全正常BFS在下一轮自然会访问它。新手容易犯的错是把“cap为0”的边直接删掉或者在做反向边更新时忘记G[v][e.rev].cap d导致反向边永远是0退流机制完全失效。如果你发现某组测试数据算出的流量偏小优先检查反向边更新是否执行了。4.3 死循环与超时的排查思路EK偶尔会死循环大多数情况下不是因为BFS写错而是因为增广路径更新环节出了问题。比如preE数组更新方向搞反了或者反向边rev下标记录错误。这里推荐一个调试技巧在循环中设置迭代上限。如果超过某个轮数还没退出手动输出当前flow和路径长度快速确认是BFS没找到汇点还是在更新环节陷入循环。比如int cnt 0; while (bfs(s, t)) { cnt; if (cnt n * m 100) { // 理论最大轮数约等于VE cout 可能出现死循环 endl; break; } // 增广代码 }理论最大轮数怎么估EK最多进行O(VE)轮增广也就是在1e5数量级内。你给自己留个几百的余量超出直接报错跑一遍就知道问题在哪。4.4 流量上限与INF的选择增广时的瓶颈值d初始化为INF这个INF不能太小否则会把正确的瓶颈值限制住。常见做法是定义为一个远大于所有边容量之和的数比如0x3f3f3f3f。如果你的流量范围可能超过int确保用long long接收结果同时INF也要定义成long long下的极大值否则累加时溢出结果会变成负数非常隐蔽。一个判断方法先看题目给的容量范围。如果单条边容量上限是1e9边数1e4最大流可能到1e13那就必须long long。4.5 重边问题的处理邻接矩阵实现时重边要自己加和否则后一条覆盖前一条。邻接表实现天然支持重边这也是我推荐邻接表的原因之一。不过要注意重边意味着两条边独立更新残余容量增广时它们会按顺序各走各的不会互相干扰。如果你读入图时预先合并重边也可以减少边数提高BFS效率这是优化点不是必选项。5. 复杂度推导O(VE²)是怎么来的以及什么时候该换Dinic5.1 每轮BFS的时间代价BFS遍历所有顶点和边在邻接表结构下每个节点出边的总和是E忽略反向边重复计整体还是O(E)量级所以每轮BFS是O(E)。求瓶颈值并更新残留网络时需要沿路径走一遍路径最多经过V-1条边每条边的更新是O(1)所以是O(V)。整体来看每轮增广的代价是O(EV)O(E)。5.2 增广轮数的上界推导前面说过如果每条边最多成为“关键边”O(V)次总的增广轮数就是O(VE)。这个证明里最关键的一步是如果某条边u→v在当前某轮增广中残余容量变成0那么为了让它再次获得容量必须存在某轮增广是沿着v→u走的。这时u→v的方向是“往回退”相当于从u到v的距离被拉长了。由于BFS每次找的都是最短路径从u到v的最短距离每经历一次“消失→恢复”至少要增加2。而任何一对节点之间的距离不可能超过V所以这条边顶多消失O(V)次。这就像一个升降梯楼层——每次某条边“消失”它的重新启用都需要以路径长度变长2作为代价。路径长度有上限V于是它不能无限消失。所以总复杂度 每轮O(E) × 轮数O(VE) O(VE²)。这是理论上界实际运行往往会远好于这个数。我在自己的测试里大部分图结构下EK的轮数都是几十到几百远达不到VE级别。5.3 什么时候换用DinicDinic算法引入分层图与多路增广单轮可以同时增广多条路径复杂度是O(V²E)在稠密图中明显优于EK。实战中的经验判断数据范围中V和E在1e3以内直接用EK代码简单好调试。V到1e4甚至更大E到1e5因为EK的VE²上界太大必须换Dinic或更高阶算法。二分图最大匹配这样的特殊结构Dinic有极佳表现EK也能过。你可以把EK当成“万能备胎”实现难度低、不容易写出隐蔽bug适合作为正确性对照实现。在我自己写Dinic的时候就经常先用EK验证小数据答案再把同样的样例丢给Dinic跑两个结果一致才放心提交。5.4 一个直观的实验数据感受用完全图做实验V20E190。EK几乎秒出结果轮数也少。V200E19900EK的每轮BFS就开始有压力了但总轮数可能还是很少。如果给一张“分层构造”的图每层之间完全连接层数很多但连接数不多EK的表现也在可接受范围内。真正能卡死EK的是那种“边数特别多且每轮只能找到很短增广路”的图这时轮数会接近理论上界算法性能肉眼可见地下降。还有一个经验如果你看到题目里的图是稀疏图E≈VEK甚至能处理上万点的规模因为每轮BFS代价很小轮数也往往不爆。稠密图才是EK的最大敌人。6. 延伸场景多源多汇、二分图最大匹配与节点容量拆分EK算法虽然简单但它的应用场景远不止“给你一张图算最大流”这么单调。很多实际模型都需要你自己动手把问题转化成最大流图。6.1 多源多汇的处理现实场景里往往有多个起点和多个终点。比如物流系统有好几个发货仓和收货仓每个仓的容量不限。处理方式是引入一个超级源点S指向所有真实源点容量设为无穷大让所有真实汇点指向超级汇点T容量也是无穷大。这样一来多源多汇就变成了单源单汇。这个做法的正确性很直观超级源点到每个源点的容量无穷大意味着不会限制从哪个源点出发最终答案就是所有源点能送出的流之和。在实际代码里这个容量一般设成一个极大数比如所有边容量之和而不是真正意义上的无穷大。6.2 二分图最大匹配的建图方式经典问题左侧有L个节点右侧有R个节点中间有一堆匹配边求最大匹配数。建图方法超级源点S - 每个左侧节点容量1 每个左侧节点 - 它能匹配的右侧节点容量1 每个右侧节点 - 超级汇点T容量1跑一遍EK得到的最大流就是最大匹配数。为什么每条匹配边的容量设为1因为每个左侧节点只能匹配一个右侧节点源点到它的容量1已经限制了它至多流1单位出去右侧到汇点容量1同理。中间容量1则对应“一条匹配边只能被选一次”。这套模型同样可以套到任务分配、课程编排等场景一类资源和一个需求之间如果能配对就加一条容量1的边。6.3 节点容量拆分的做法有时候不只是边有容量节点本身也可能有吞吐限制。比如中转站一天最多处理多少货物。处理方法是将节点u拆成u_in和u_out两个点u_in到u_out连一条容量等于节点容量上限的边。所有原来进入u的边连到u_in所有原来从u出去的边从u_out出发。道理很简单所有流量都必须经过u_in→u_out这条“闸门”闸门容量限制住了整个节点的流量总量。我在处理带节点容量的问题时经常用这个方法配合EK模板非常好使。6.4 网络流建模的通用思路总结面对一个实际问题我一般先问自己三个问题谁在“流”是货物、信号、人还是数据起点和终点分别是什么是多个还是单个约束在哪里是边的容量约束还是节点的容量约束把这三个问题想清楚建图基本就完成一半了。另一半是处理特殊约束多个起点加超级源点多个终点加超级汇点节点容量就拆点。这个套路几乎覆盖了我见过的绝大多数流量类问题。EK算法在其中扮演的角色不只是一个模板更是一种思考框架——它逼着你先建模再套算法而不是上来就调库。我在实际用EK算法过程中最大的体会是不要因为它是“入门算法”就轻视它恰恰是这种结构简单的算法最容易让人把基础概念吃透。反向边怎么退流、残留网络为什么这样更新、BFS路径长度为什么单调这些一旦搞明白后面学Dinic、最小费用最大流都会顺很多。建议你把上面那个邻接表模板多跑几个例子手动模拟几轮增广过程亲手体会一下流量如何通过反向边“反悔”这比背十遍原理都管用。