1. 网络流到底在解决什么问题第一次接触网络流的人脑子里蹦出来的画面通常是水管。这个直觉其实相当准确。把一张有向图想象成一套管道系统每条边就是一根管子管子有粗细也就是容量单位时间内能通过的水量有上限。源点就是总进水口汇点就是总出水口中间那些节点就是管道交汇处。水从源点灌进去经过各种分叉和汇合最终从汇点流出来问的是这套系统单位时间内最多能流过去多少水这就是最大流问题的生活化版本。但网络流能干的远不止算水管。物流配送里货物从仓库到各个配送站再到用户手里每条运输线路有运力上限怎么安排路线让总配送量最大通信网络里数据包从发送端到接收端每条链路有带宽限制怎么调度让吞吐量最高甚至任务分配场景一批工人和一批任务每个工人能胜任其中几项怎么匹配让完成的任务数最多——这些全是最大流的变体。我当年学网络流的时候最大的困惑不是算法本身而是“为什么这个问题值得单独发明一套算法”。后来做项目才明白很多看似八竿子打不着的问题建模成网络流之后解法就变得极其统一。你不需要为每个场景重新设计算法只需要把问题翻译成图然后调用同一套最大流求解器。这种“建模一次到处复用”的特性是网络流最迷人的地方。这篇文章面向的是刚入门或者准备入门网络流的开发者。我会从最朴素的思路讲起把EK算法和Dinic算法的来龙去脉拆开揉碎配上可以直接跑的代码和参数选择的经验最后聊聊实际做题和做项目时踩过的坑。不需要你有图论基础但需要你会写基本的循环和递归能看懂简单的队列和数组操作。2. 从贪心到残量网络最大流的核心思想拆解2.1 为什么简单的贪心会翻车最直觉的想法是这样的从源点出发随便找一条到汇点的路径路径上每条边都还有剩余容量那就往这条路径上推流推的量等于路径上最小的剩余容量。推完再找下一条直到找不到为止。这个思路叫“增广路”思想方向是对的但单纯的贪心会出问题。举个例子源点S连到节点A和节点BA连到汇点TB也连到T同时A和B之间有一条边。假设S到A的容量是1S到B的容量是1A到T的容量是1B到T的容量是1A到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→TS到B还有1的容量B到A走反向边相当于把之前A→B的流量退回去A到T还有1的容量。这条路径推1的流量后净效果是S→A→T走了1S→B→T走了1总流量变成2。反向边让算法自动修正了之前的错误选择。注意反向边的容量是动态变化的。当你通过反向边推流时相当于减少了正向边的已用流量所以正向边的残量会增加反向边的残量会减少。这个联动关系在代码里必须严格维护写错一个方向就会导致死循环或者结果偏小。2.3 增广路定理什么时候算到头不断找增广路直到残量网络中不存在从源点到汇点的路径为止。这时候得到的流量就是最大流。这个结论叫“增广路定理”是最大流算法的理论基石。为什么找不到增广路就等于最大流直观理解如果残量网络中源点到汇点不可达说明当前流量已经把网络“割断”了。把所有从源点可达的节点划成一个集合S其余节点划成集合T那么从S到T的所有边的残量都为零也就是说这些边全部满载。这些满载边的总容量等于当前流量而任何可行流都不可能超过这个割的容量所以当前流量就是最大流。这个定理的美妙之处在于它把“最优性判断”转化成了“可达性判断”。你不需要证明当前流是最优的只需要跑一遍搜索看看还有没有路。没有路就是最优。3. EK算法最直观的增广路实现3.1 EK算法的执行流程EK算法Edmonds-Karp算法的思路极其朴素每次用BFS找一条增广路找到就推流推完继续找直到BFS找不到路径为止。BFS的作用是保证每次找到的增广路是“边数最少”的那条。具体步骤拆解初始化所有边的残量为原始容量反向边残量为零。从源点开始BFS记录每个节点的前驱节点和前驱边的编号。如果BFS能到达汇点说明存在增广路。沿着前驱数组从汇点回溯到源点找出路径上残量最小的值记为delta。再次沿着路径正向边残量减delta反向边残量加delta。累加总流量重复步骤2到4。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 flowdfs函数的返回值是本次增广推的流量。如果返回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的选型对比对比维度EK算法Dinic算法增广方式每次BFS找一条增广路每次BFS后DFS找多条增广路时间复杂度O(VE²)O(V²E)适用场景节点数200的小图节点数5000的中大型图代码复杂度低容易手写中等需要当前弧优化单位容量图O(VE)O(E√V)实际表现边多时明显慢大多数场景下很快选型建议很直接除非图特别小节点数几十个否则一律用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汇点固定为n1中间的业务节点从1到n。这样源点和汇点永远不会和业务节点冲突。邻接表用列表的列表实现graph [[] for _ in range(n2)]。每个元素是一个Edge对象列表。添加边的时候正向边和反向边成对添加确保rev索引正确。数组初始化方面level数组每轮BFS前重置为-1iter_arr数组每轮BFS后重置为0。这两个重置如果漏掉会导致结果错误或者死循环。我踩过的坑是把iter_arr的重置放在了DFS内部结果每轮DFS都从头开始探索当前弧优化完全失效程序跑得比EK还慢。5.3 调试技巧小图手算验证写完最大流代码后不要急着跑大数据。先构造一个5到6个节点的小图手算最大流然后和程序输出对比。小图能暴露大部分逻辑错误比如反向边更新方向反了、BFS层次计算错了、DFS回溯条件写错了。我常用的测试图是一个经典的“菱形加交叉”结构S→A容量3S→B容量2A→B容量1A→T容量2B→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算法Dinic算法100节点1231000节点超时30秒455000节点超时320EK算法在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 常见问题速查表问题现象可能原因排查方法解决方案结果偏小反向边未更新打印残量网络检查rev索引和更新方向死循环level条件错误打印DFS路径严格使用level[v]level[u]1死循环iter_arr未递增打印iter_arr在while循环末尾递增结果偏大容量初始化错误检查建图代码确认正向边容量和反向边为0超时用了EK算法看节点规模换Dinic加当前弧优化栈溢出递归太深看递归深度改迭代或增大限制答案不稳定多组数据未重置检查全局变量每组数据重新初始化6.5 独家避坑技巧第一个技巧建图时给每条边加一个id字段调试时打印边的时候能直接定位到是哪条边。这个id在最终代码里可以去掉但调试阶段非常有用。第二个技巧用assert检查关键不变量。比如每次推流后检查正向边残量加反向边残量是否等于原始容量。这个检查能第一时间发现更新错误。第三个技巧对于二分图匹配问题不要直接用最大流可以用匈牙利算法。虽然Dinic也能做但匈牙利算法代码更短常数更小。当然如果匹配问题带权或者带其他约束还是得回到最大流。第四个技巧如果图中有重边邻接表里会有多条相同起点终点的边。这本身没问题但要注意rev索引的对应关系。添加重边时每条边都有自己独立的反向边不要试图合并。7. 最大流的扩展玩法与实战建议最大流本身是一个工具真正有意思的是它的变体。最小割问题就是最大流的对偶问题根据最大流最小割定理最大流的值等于最小割的容量。很多“破坏最少边让图不连通”的问题直接跑最大流就出答案。费用流是在最大流的基础上给每条边加了单位费用要求在流量最大的前提下费用最小。解法是把BFS换成SPFA或者Dijkstra配合势能函数每次找费用最小的增广路。费用流的代码比最大流长不少但核心思想一脉相承。上下界网络流是给每条边加了流量下界要求流量必须在一个区间内。这个变体需要先做一次“可行流”判断再跑最大流。建图方式比较绕但套路固定做两道题就能记住。对于准备刷题的朋友我的建议是先把Dinic模板写熟做到不看参考代码能在15分钟内写出来并且一次通过。然后按专题刷先刷纯最大流再刷最小割再刷二分图匹配最后刷费用流。每个专题刷10到15道题基本就能形成肌肉记忆。对于做工程的朋友最大流的应用场景比想象中多。资源调度、任务分配、网络优化、甚至推荐系统中的多样性控制都能建模成最大流。关键是要有“把问题翻译成图”的意识这个能力比会写Dinic代码更重要。我在实际项目里用最大流解决过一个日志采集的调度问题多台采集机往多个存储节点发送数据每台采集机有发送上限每个存储节点有接收上限采集机和存储节点之间的链路有带宽限制。建图跑Dinic直接得到最优调度方案。整个方案从建模到上线不到两天比手写贪心调度稳定得多。最后分享一个学习路径先理解增广路和残量网络的概念然后手写EK算法跑通小图再改写成Dinic算法加上当前弧优化最后刷题巩固。整个过程快的话一周慢的话两周。关键是不要跳过手写EK这一步直接抄Dinic模板虽然能过题但遇到变形题或者需要调试的时候没有EK的基础会非常吃力。
