网络流这名字听起来像什么高深的理论但说白了它解决的问题非常朴素在一个有容量限制的输送网络里从源头到终点最多能同时送多少量。我第一次被最大流震撼到不是因为它能算出答案而是因为一道看起来跟“管道运输”毫无关系的题目稍微转了个弯就变成了最大流模型。从那之后我就明白一件事最大流不只是一个算法更是一套把各种约束翻译成图的“建模语言”。这篇文章不打算从教科书定义开始念直接以“最大流判定、拆点、建图实战”为主线把我这些年做最大流题的真实经验、常用套路和踩过的坑全部梳理一遍。不管你是刚接触网络流的初学者还是已经能默写 Dinic 但一到建模就卡壳的选手这篇文章都值得你从头读到尾——最后那部分避坑清单能帮你省下好几个通宵。1. 先搞清楚最大流到底在求什么1.1 水管网络的抽象模型先讲个最简单的例子。假设你有一个供水系统自来水厂是源点小区是汇点中间有一堆水管和泵站。每根水管有直径单位时间最多能过多少水这就是“容量”水泵可以决定水流往哪走但不能让水凭空产生也不能让水在某处越积越多——这就是“流量守恒”。把这种直觉翻译成数学语言一个流网络就是一张有向图每条边有一个非负容量 c(u, v)源点 s 只能流出汇点 t 只能流入中间每个点进出总量必须相等。最大流问题问的就是在满足所有容量限制和守恒条件的前提下从 s 到 t 能送过去的最大总量是多少。这个模型最妙的地方在于它不只适用于水、电、油这类物理输送。信息流、资金流、物流、任务分配甚至人的流动只要满足“有起点有终点、中间有容量限制”这个结构都可以套进来。1.2 最大流判定不是在问“流到多少”而是在问“能不能”标题里的“最大流判定”其实包含两层意思很多人做题时只注意到第一层。第一层是可行性判定。有些题目不会直接问你最大流是多少而是问“能不能在某个容量限制下达到至少 K 的流量”或者“是否存在一种分配方案满足所有需求”。这类问题本质上是判断“最大流是否大于等于某个阈值”把阈值当参数跑一遍最大流比较一下结果就可以了。很多判定类问题的答案带有单调性还能配合二分答案使用枚举一个参数建图跑最大流看能不能满足条件。这个过程就叫“二分 最大流判定”是网络流题目里最高频的组合之一。第二层是校验判定。你写完了 Dinic怎么确定自己跑出来的是对的我的习惯是用最大流最小割定理做交叉验证最大流的值一定等于最小割的容量而最小割可以单独用一次 DFS/BFS 在残量网络上算出来。如果两个结果对不上说明你的模板或者建图有问题而不是算法有问题。这两种“判定”在后面的章节里都会涉及到先记在脑子里。1.3 什么样的题目适合用最大流我总结了一个很实用的经验一道题如果同时出现以下特征多半是在考网络流。题目里有明显的“运输、分配、配对、覆盖、切割、阻止”这类动作有多组起点和终点存在“每个单位/容量限制”答案是一个数值最大多少、最小多少而不是具体方案数据范围通常不大点数在几十到几千这种量级。反过来如果题目只是问你“图上两点连通吗”“最短路径是多少”那用 BFS 或者最短路就行不要去套网络流。建模的第一步不是想用什么算法而是判断这道题到底是不是网络流题。判断错了后面全白搭。2. 算法选型与实现Dinic 为什么够用2.1 从增广路到分层图最大流的算法说起来都是围绕一个核心概念增广路。在残量网络上找到一条从 s 还能走到 t 的路径把流量沿着这条路推过去直到找不到这样的路径为止。问题在于找增广路的策略不同复杂度天差地别。最简单的是 Ford-Fulkerson 方法每次用 DFS 随便找一条增广路。它的问题是如果容量是整数而且很大增广次数可能多到无法接受最坏情况是 O(E * maxflow)一旦流量上亿就彻底歇菜。Edmonds-Karp 改进了这一点每次用 BFS 找最短的增广路复杂度变成了 O(V * E^2)稳定是稳定但在竞赛和工程场景下依然偏慢。Dinic 算法则往前走了一大步。它先 BFS 一次把整个残量网络按到源点的距离分层然后在分层图里用 DFS 一次找多条增广路直到这一层网络里再也推不动流量为止。这个“推不动”的状态叫阻塞流。Dinic 的复杂度是 O(V^2 * E)但实际运行速度远好于这个上界在大多数题目里是首选。2.2 一个能直接用的 Dinic 模板下面这个模板我用了很多年结构清晰适合学习也适合直接抄去比赛。struct Edge { int to, rev; long long cap; }; vectorEdge g[MAXN]; int level[MAXN], iter[MAXN]; void addEdge(int u, int v, long long cap) { g[u].push_back({v, (int)g[v].size(), cap}); g[v].push_back({u, (int)g[u].size() - 1, 0}); } bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (const auto e : g[u]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[u] 1; q.push(e.to); } } } return level[t] 0; } long long dfs(int u, int t, long long f) { if (u t) return f; for (int i iter[u]; i (int)g[u].size(); i) { Edge e g[u][i]; if (e.cap 0 level[e.to] level[u] 1) { long long d dfs(e.to, t, min(f, e.cap)); if (d 0) { e.cap - d; g[e.to][e.rev].cap d; return d; } } } return 0; } long long maxFlow(int s, int t) { long long flow 0; const long long INF 1LL 60; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); long long f; while ((f dfs(s, t, INF)) 0) { flow f; } } return flow; }这里有个关键点要注意addEdge里必须同时加入反向边容量初始为 0。反向边不是摆设它代表“反悔”的能力——当一条边的流量被占用了通过反向边可以把流量退回去重新分配给别的路径。没有反向边所有贪心式的推进都会出错。2.3 当前弧优化到底优化了什么很多初学者看不懂iter这个数组是干什么的。它的全名叫“当前弧”作用是记录每个点当前 DFS 已经遍历到哪条边了。想一下这个场景在一轮 BFS 分层之后我们要反复调用 DFS 来寻找阻塞流。如果一个点的某条出边已经被尝试过并且没能推进任何流量那在这同一轮 DFS 里再碰这条边也大概率还是失败因为残量或者层级条件没有变。iter[u]让我们直接从上次结束的位置继续而不是每次从头遍历。这个优化看起来不起眼但实测下来能把 DFS 的边扫描次数从 O(E) 降到接近 O(增广路数)是 Dinic 性能的关键。还有一个容易忽略的细节iter数组必须在每一轮 BFS 之后重新清零因为分层图变了之前“推不动”的边在新的分层图里可能又能推了。3. 拆点把点容量变成边容量3.1 点也会“堵”这就是拆点的动机教科书里的流网络只给边加了容量但现实世界里的约束往往落在点上。比如一个中转站一天只能处理这么多货物一座城市只能承载这么多车流一个服务器只能运行这么多任务。这些限制都发生在“点”上而标准最大流模型只认边容量怎么办拆点就是答案。思路特别朴素把每个有容量限制的点 v 拆成两个点一个叫入点 v_in一个叫出点 v_out。原来所有指向 v 的边都改成指向 v_in原来从 v 出发的边都改成从 v_out 出发然后在 v_in 和 v_out 之间连一条容量为点容量的边。这样一来任何流要想“经过”这个点就必须先钻进 v_in再挤过那条代表容量上限的边从 v_out 出来。点约束就干干净净地转化成了边约束。用一个生活化的类比原来的点是一个可以随意进出的大广场拆点之后变成了一个带安检门的通道门多宽单位时间能过多少人就是点容量。3.2 拆点的标准姿势与细节具体操作上拆点有两种编号习惯。一种是把点 i 拆成 i 和 i N其中 N 是原图点数这种写法直观好调试另一种是拆成 i * 2 和 i * 2 1适合在某些图论框架里统一处理。我一般推荐第一种理由很简单建图的时候不容易把编号算错。标准建图流程分三步。第一步对于每个需要限制容量的点 i加一条边 i - i N容量为点容量。第二步原图的每条有向边 u - v容量为 w改成 u N - v容量为 w。第三步源点和汇点如果不需要限制容量对应拆点边的容量设成无穷大就行。这里有几个容易踩的坑。第一原边方向不能搞反一定是“出点连入点”也就是 u N - v。第二如果是无向图每条无向边要拆成两条方向相反的有向边分别按规则连。第三拆点之后点的总数翻倍数组大小一定要开够少开一个 0 就是数组越界在评测环境里表现非常阴间。3.3 一个拆点实战案例给一个特别经典的题目模型有 N 个点和 M 条有向边每条边有一个容量每个点除了起点和终点有一个允许经过次数的上限问从点 s 到点 t 最多能输送多少流量。看完第一反应可能是懵的点限制和边限制混在一起怎么处理用拆点就清晰了。我建图的时候会这样写// 假设点编号 1..N拆点后入点为 i出点为 i N for (int i 1; i N; i) { int cap (i s || i t) ? INF : nodeCap[i]; addEdge(i, i N, cap); } for (int i 0; i M; i) { // 原边 u - v容量 w addEdge(u N, v, w); } long long ans maxFlow(s N, t);注意最后跑流的起点是s N而不是s终点是t而不是t N。原因是起点要能往外发流必须从它的出点出发终点要能收流必须从它的入点进入。很多新手在这里搞反导致答案永远为 0检查大半天才发现是端点编号错了。这个模型还可以延伸出很多变体如果允许同一点多次经过但不允许重复走同一条边点容量设成无穷大、边容量设成 1 即可如果要求“每个点恰好经过一次”点容量设成 1就变成了路径覆盖类问题。拆点可以说是网络流建模里最基础也最万能的一招。4. 建图实战从题目到网络的转化套路4.1 超级源点与超级汇点有些问题不止一个源点或者不止一个汇点。比如有 3 个仓库、5 家超市每种商品从任意仓库都能往任意超市送问最大能送多少。直接跑最大流没法做因为 Dinic 只支持单一源点和单一汇点。解决方案是加一个“虚拟源点” S从 S 向每个仓库连一条容量为仓库库存的边再加一个“虚拟汇点” T从每家超市向 T 连一条容量为超市需求的边。这样整张图就变成了一张标准的单源单汇网络。超级源和超级汇的本质是“把多个外部约束统一入口”。这个思想在建图里反复出现比如带时间维度的动态网络流问题每一层的入口也可以共用一个超级源来汇总。它的实现没有任何技术难度难的是意识到“这里需要加一个虚拟点”。有人可能会问为什么不直接把多个源都当成同一个点答案是不行。如果两个源点直接合并它们的内部流量会互相串容量约束就失效了。超级源点通过单独的边把每个源点隔开既保留了各自的容量限制又统一了计算入口这才是它的价值。4.2 二分图模型的三种变体最大流建图里最经典的一类就是二分图模型。左部点集合 L右部点集合 R源点 s 连所有 L所有 R 连汇点 t中间的边容量设 1跑出来就是最大匹配数。这个模型虽然简单但变形很多。第一种变体是多重匹配。如果每个左部点可以匹配多个右部点把 s 到 L 的边容量从 1 改成 k 即可右部点同理。这类问题常见于“一个老师可以带多个学生但每个学生只能选一个老师”的场景。第二种变体是网格染色。很多棋盘上的题目把格子按棋盘黑白染色后相邻格子天然形成二分图。如果题目限制相邻格子不能同时选那就是求二分图最大点权独立集。这类题最典型的解法是“总权值减去最小割”关于这一点下一小节展开说。第三种变体是最小路径覆盖。给定一个 DAG问最少用多少条不相交路径能覆盖所有点答案是“点数减去最大匹配数”。建模方式是把每个点拆成两个点放在二分图两侧原图有边 u - v 就连接 u_left 和 v_right。这里其实就是把拆点和二分图结合起来了你能看到这两个技巧从来不是孤立的。4.3 最小割最大流的“另一半”最大流最大流光会说“流”是不够的它的对偶问题“割”同样重要。很多人学到最小割定理就停在背结论其实不同建模方向能解决完全不同的问题。最小割问题定义是把图分成 S 和 T 两部分源点在 S 里、汇点在 T 里所有从 S 连到 T 的边的容量之和就是割的容量找一个最小的割。最大流最小割定理保证两者相等所以跑一遍最大流就能知道最小割容量是多少。但最常用的不是求割本身而是利用“最小割 损失的最小代价”这个巧妙等价关系解决“选择”类问题。最典型的是“方格取数”一个棋盘每个格子有价值要求取一些格子但不能同时取相邻的两个问最大能取的价值。正面思考很难反过来想先把所有格子价值加起来如果选了冲突就要付出代价问题变成“最少放弃多少价值”。建图方式是黑白染色源点连黑点容量为价值白点连汇点容量为价值相邻的黑白格子之间连无穷大边。最小割会把一些格子从“选”变成“不选”答案就是总价值减去最小割。这个套路叫“最大权闭合子图”的最小割建模可以用来解项目选择、依赖关系、冲突取舍一大类问题。到这里你应该能感觉到建图能力强不强归根结底是能不能把题目里的“限制关系”翻译成“割的关系”。5. 常见问题与避坑指南5.1 那些调了一晚上才发现的 bug网络流题的 bug 很有特色报错方式千奇百怪很多都是逻辑正确但细节翻车。我把这些年踩过的坑按频率排了个序做成一张速查表。症状常见原因处理办法答案偏小INF 取值太小流量被截断INF 至少取 1e18long long答案永远为 0源点/汇点编号写错跑的是拆点后的错误端点核对起点应从出点出发、终点应在入点接入程序 RE 或崩溃数组大小没按拆点翻倍点容量、边数组统一乘 2死循环或卡死反向边容量忘记增加检查addEdge里有没有同步更新反向边结果异常大流量累加用了 int溢出全部改成 long long答案比预想大一点BFS 分层条件没写cap 0残量为 0 的边不能走多次运行结果不一致iter没有每轮重置每次 BFS 后清零当前弧我最惨的一次经历是二分答案 最大流判定的题debug 到凌晨两点最后发现是建图时原边方向写反了。从那之后我养成了一个习惯每次建完图先抽取几条关键路径手算验证边的方向和容量再交代码。这个方法看起来笨但比任何调试工具都可靠。5.2 跑不动的网络流性能优化与常数控制Dinic 虽然快但碰上大规模数据还是可能超时。如果你确认建图没问题性能却不达标试试下面几招。第一招是改用链式前向星存边不用 vector。vector 每次 push_back 都有分配开销边多的时候影响明显。链式前向星用两个数组模拟邻接表内存连续Cache 友好能省不少常数。第二招是尽量减少 DFS 的递归深度和无效调用。当前弧优化一定要写而且dfs里如果某条边返回了 0不要立刻放弃整个函数要继续尝试下一条边因为可能只是这条边残量为 0别的边还有机会。第三招是针对特殊图选择算法。稠密图、二部图等特殊结构有更专门的算法比如二分图最大匹配直接用匈牙利算法反而更快完全没必要绕道最大流。判断数据规模点数超过 1e5、边数超过 1e6 的题多半不是让你跑一般网络流的要么有特殊性质可以用别的算法要么换建模思路。5.3 判断要不要用网络流先想清楚这三件事最后这点我特别想强调。网络流是很强但它不是万能钥匙更不是越高级越好。拿到题先问自己三件事。第一问题的约束能不能表达成容量如果题目里的限制是“最多发生一次”“最多占一个名额”这种可以如果限制是“必须连续”“必须满足某种顺序”那网络流大概率处理不了得另找思路。第二数据规模撑不撑得住一般 Dinic 在几千点、几万边的规模下表现很好但如果点数是百万级常规网络流大概率超时这时候应该去观察这张图有没有特殊结构比如是不是树、是不是二分图、是不是平面图。第三你需不需要具体方案而不仅仅是数值最大流通常给你的是流量值要还原具体每条边流了多少得从残量图里反推。如果题目要求输出具体的配对方案、分配方案确实可以做到但要在建图时就做好记录设计别等跑完流再临时抱佛脚。我个人在实际操作中的体会是网络流建模最考验的不是算法知识而是“抽象能力”——把题目里的每个人、每件物、每个限制翻译成节点和边。拆点、超级源汇、二分图、最小割这些套路本质上都是在做同一件事把复杂约束翻译成图的语言。翻译得顺代码反而是最简单的部分。最后再分享一个小技巧每道题跑完最大流之后我会拿最小割的边集对着题目要求验证一遍。最小割里被切掉的边对应的就是题目里“被放弃”的资源看着这些边你能直观地发现自己建图时有没有漏掉约束。这个习惯帮我发现过好几次建模错误希望你也能用上。