先交代一个背景我刚接触网络流那会儿连“为什么拆点之后原来的边要连到入点从出点连出去”都绕了很久才想通。等到真正动手刷题、写板子才意识到最大流这一章最值钱的部分不是背模板而是会用“判定”的思路去转化问题、会用“拆点”去处理点容量、会把一个陌生问题一点点掰开揉碎变成一张能跑的图。这篇就把我实际用到的三板斧——最大流判定、拆点、建图实战——完整讲透结合题目和代码一起说。1. 先把最大流的模型和“判定”这件事理清楚1.1 标准最大流模型到底在做什么最大流问题看着简单给一个有向图每条边有一个容量上限然后从源点 S 到汇点 T 运输“流量”问最多能运多少。但真正刷题的时候你会发现题目几乎不会直接说“给你一张图求最大流”而是给你一个实际问题让你自己抽象成图。这里要把握住三个约束容量限制每条边的流量不超过容量、流量守恒除源点和汇点外每个点的流入量等于流出量、反对称性从 u 到 v 的流量是正的则从 v 到 u 的流量是负的。所有最大流算法都是在这三个约束下求可行流的最大值而 Dinic、ISAP 这些算法本质上都是在不断寻找增广路把流量逼近最大。有一个很重要的直觉最大流问题的本质是“资源在容量约束下从供给端到需求端的最优分配”。所以调度、匹配、路径规划、电路分析里大量问题都能套进这个框架。1.2 “最大流判定”到底是什么很多人看到“判定”两个字就懵了以为是另一种算法。其实在竞赛和实战里“最大流判定”通常指两类场景。第一类是把判定问题转化为最大流比如给定一些约束条件问“是否存在一种分配方案”这时候我们往往建一个图跑最大流看最大流是否等于某个目标值。最典型的就是二分图最大匹配左侧点连右侧点每个点容量为 1源点连所有左侧点、右侧点连汇点如果最大流等于左侧点的数量就说明所有左侧点都能匹配上这是一个“完美匹配判定”。第二类是让最大流本身去判定某个参数是否可达典型做法是二分答案把“可行性”判定拆成多次最大流。比如我们要找一个最小的时间 T让所有任务都能在 T 内完成那我们可以对 T 二分每次用最大流判定当前 T 下是否存在可行方案。这里要给一个核心结论最大流跑出来的结果不仅仅是一个数它可以作为“可行性判定的裁决器”。只要你能把“可行”等价转换成“存在一个流使得某个值达到 X”那么最大流就是你的判定函数。这个思维方式比写模板重要得多。1.3 判定问题的通用构图套路我自己的习惯是先回答三个问题再动手建图谁是源谁是汇——源代表供给汇代表需求。什么限制是“容量”——容量代表资源上限可能是时间、人数、流量。目标是什么——通常是让某个量达到最大或者让某个量等于某个值。举个例子现在有 n 个工作m 台机器每个工作需要某种机器资源每台机器同一时间只能处理一个工作问最多能同时开工多少个工作。这就是个二分匹配判定源点连工作工作连能用的机器机器连汇点所有容量为 1跑最大流结果就是最多能同时开工的工作数。很多看起来不像是“流量”的问题一旦你找到这三个问题的答案图就自动出来了。2. 拆点从“点容量”到“边容量”的转化魔法2.1 拆点要解决什么问题网络流的容量是定义在边上的但有一类问题限制的是点比如一个城市节点最多只能通过 C 辆卡车一个服务器节点最多只能处理 D 个请求一个中转站最多只能中转多少货物。这些情况下我们没有办法把“点容量”直接写进标准最大流模型因为算法的增广操作是沿着边走、对边容量做减法它并不知道“点”有容量。解决方案就是拆点把某个节点 i 拆成 i_in入点和 i_out出点然后在这两个点之间连一条容量为点容量的边。这样所有进入原节点 i 的流量必须先流进 i_in再通过那条容量受限于点容量的边到达 i_out才能继续流出。点的限制就变成了中间那条边的容量限制。这个技巧的本质是把一个“点的容量约束”等价转化成一个“边的容量约束”让标准算法可以处理。2.2 拆点的标准姿势拆点的时候我一般这样操作给每个原节点 i 分配两个编号比如i和i n假设原图有 n 个节点。从i入点到i n出点连一条容量为c_i的边——这就是点容量。原图中所有从 u 到 v 的边改造为从u nu 的出点连到vv 的入点的边容量不变。连接关系很好记“入边连入点、出边从出点出、中间边管容量”。如果点本身没有容量限制中间那条边的容量设为INF也行这样它不会成为瓶颈。注意一个坑如果你把中间点容量边设成 0等于这个点完全不可用设成 INF等于没有点容量限制。但千万别漏掉这条边否则入点和出点之间是断开的流量根本出不去。我第一次做拆点时就在这上栽了跟头。2.3 拆点的经典场景分层图与路径限制拆点不只是用来处理点容量的它还能处理更复杂的结构。一个常见场景是“不允许经过同一个节点两次”的路径问题。比如问一条从 S 到 T 的路径最多能经过多少不同的点或者求 S 到 T 的不相交路径数。这时候我们拆点让除源和汇以外的每个节点中间容量为 1那么一条增广路就相当于一条路径中间容量为 1 意味着这条路径不能重复使用同一个节点。跑最大流得到的结果就是最多能找到多少条节点不相交的路径。另一个是“分层图”思路当流量带有时间维度比如在 t 时刻到达某个节点我们可以把每个节点按时间拆成多层每层代表一个状态。虽然这不完全是传统拆点但核心思想一致——多个状态或者多个限制维度就用拆点/分层把它展开到图上。2.4 拆点与费用流、最小割的联动拆点也不仅限于最大流。在费用流里面如果每个节点有一个“处理成本”或“处理上限”同样可以拆点在入点和出点之间连一条带费用的容量边每单位流量经过该点就要付出对应的费用。而在最小割问题里拆点能用来表达“删除一个节点的代价”把节点拆成入点出点中间边的容量就是删除这个节点的代价割掉这条边就等价于删除这个节点。记住一句话拆点把“节点”的语义变成“边”的语义一旦变成了边容量、费用、割代价都可以往上挂。这是拆点最大的价值——不是解决某个具体问题而是统一地把一类问题纳入网络流的可处理范围。3. 建图实战四个经典问题的手把手建模这一节是重头戏我不讲虚的直接上四个实战场景从易到难每个都给出完整的建图思路、容量设定、以及为什么这样建。3.1 二分图最大匹配与完美匹配判定问题背景有 n 个求职者和 m 个岗位每个求职者能胜任其中若干岗位一个岗位只能招一个人问最多能安排多少人上岗。建图方案建超级源点 S超级汇点 T。从 S 向每个求职者 i 连一条容量为 1 的边。从每个岗位 j 向 T 连一条容量为 1 的边。如果求职者 i 能胜任岗位 j从 i 向 j 连一条容量为 1 的边这里不用拆点因为人和岗位都天然带点容量 1且没有中间传递。跑一遍最大流流量大小就是最多能安排的人数。如果最大流等于 n说明所有求职者都能安排到岗位这就是“完美匹配判定”。这里有一点值得展开为什么用最大流而不是直接贪心匹配因为二分图匹配有一个“重新分配”的过程贪心会陷入局部最优而最大流的增广路机制天然允许反悔。这也是 Dinic 比朴素的贪心匹配更稳妥的原因。3.2 带节点容量的一般网络最大流问题背景一张有向图除了边有容量每个中转节点非源非汇最多只能通过 C_i 的流量求源到汇的最大流。这个问题的场景非常常见比如一个物流网络每个仓库有吞吐上限。建图方案就是在普通图上加拆点把所有中间节点 i 拆成 i_in 和 i_out。i_in 到 i_out 连容量为 C_i 的边。原图中边 u - v容量 cap改造为 u_out - v_in容量 cap。源点 S 可能没有入度但仍把它拆成 S_in 和 S_out或者直接用 S_out 作为源汇点 T 同理用 T_in 作为汇。跑最大流结果就是全局最大流量。我建议在做这类题时先画一张改造前后的图对比一下改造前是“点重叠”“边相连”改造后变成了“点拆开”“边串过”。画一遍之后对拆点的理解会彻底稳固。3.3 有向无环图的最小路径覆盖问题背景给定一个 DAG问最少需要多少条路径路径间不能相交即不能共用节点才能覆盖所有节点。这个问题的答案是节点数 - 最大匹配数。这个结论看起来是从图论里来的但它的证明和实现都依赖网络流/二分图匹配。建图方案把每个节点 i 拆成左点 i出点和右点 i入点形成一个二分图。如果原图有边 u - v则在左点 u 和右点 v 之间连一条容量为 1 的边。超级源 S 连所有左点容量 1所有右点连超级汇 T容量 1。跑最大流得到最大匹配数最小路径覆盖数 n - maxflow。为什么是这个公式直观理解一开始每个点都是一条单独的路径总共 n 条。每匹配一对 u-v就相当于把“以 u 结尾的路径”和“以 v 开头的路径”拼接起来路径总数减 1。拼接不能重复用节点所以每个左点、右点都只允许匹配一次容量为 1 正好满足。3.4 多源多汇与超级源汇的合并问题背景有时候源点和汇点不是单一的一个而是多个。比如有 3 个仓库、5 个销售点要给每个销售点送货。我们不可能把最大流算法扩展到多源多汇算法要求的是一对一源汇最然存在变体但最稳妥的方式是合并最简单的做法是加一个超级源和超级汇。建图方案新增 S* 和 T*。S* 向每个原有仓库源点连一条容量为对应仓库供货能力的边。每个原有销售点汇点向 T* 连一条容量为对应销售点需求量的边。原始图中源和汇的语义就消失了统一变成了普通节点整个图变成一个单一源汇的最大流网络。这里有个技巧如果某个销售点的需求量是 D连 D 容量如果仓库供货能力不确定连 INF。跑完后流量就是总供货量。如果要判定“能否满足所有需求”就看 maxflow 是否等于所有需求之和。3.5 最大权闭合子图拆点延伸到最小割这个问题稍微偏最小割一点点但在建图实战里非常经典。问题背景有 n 个项目每个项目有收益可能为正也可能为负项目之间有依赖关系做项目 A 必须先做项目 B选一些项目使得总收益最大。这个问题用最大流等效于最小割解决。建图方案对于收益为正的项目 i从 S 向 i 连容量为收益的边。对于收益为负的项目 j从 j 向 T 连容量为 -收益即代价的边。依赖关系 u 必须先于 v从 u 向 v 连一条容量为 INF 的边。答案 所有正收益之和 - 最小割即最大流。割的含义割掉 S 到正收益的边表示放弃这个项目割掉负收益到 T 的边表示承担这个项目的成本。INF 边保证依赖不会被破坏。这也是为什么“最大流 最小割”这个对偶关系在实战中极其重要——有些问题适合从“最大流”角度想有些适合从“最小割”角度想但代码上跑的是同一个算法。4. Dinic 板子、复杂度与避坑清单4.1 一份带注释的 Dinic 实现网上板子很多但很多对新手不友好我贴上我自己一直在用的版本加了比较详细的注释#include bits/stdc.h using namespace std; const int N 1005; const long long INF 1e18; struct Edge { int to; // 边的终点 long long cap; // 剩余容量残量 int rev; // 反向边在邻接表中的下标 }; vectorEdge g[N]; int level[N], iter[N]; // level: BFS分层 iter: 当前弧优化指针 void add_edge(int u, int v, long long cap) { // 正向边 g[u].push_back({v, cap, (int)g[v].size()}); // 反向边初始容量为 0 g[v].push_back({u, 0, (int)g[u].size() - 1}); } // BFS 构建分层图返回是否能从 s 到达 t 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 (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] ! -1; } // DFS 在分层图中寻找增广路返回实际增广的流量 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[u] level[e.to]) { 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 max_flow(int s, int t) { long long flow 0; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); while (true) { long long f dfs(s, t, INF); if (f 0) break; flow f; } } return flow; }这个板子的几个细节值得注意反向边容量等于正向边已经使用的流量这是匈牙利增广的一种形式化给算法提供“反悔”能力。level[u] level[e.to]是保证 DFS 只在分层图上沿着层数递增的方向走防止死循环。iter[u]是当前弧优化代表从 u 出发的边里哪些已经用尽了残量为 0下次直接从下一条开始避免重复遍历已经没有流量的边。INF设成1e18并且用long long是因为网络流题目里容量经常给到 1e9若干条边叠加后可能会超过 int 上限。4.2 时间复杂度和实际表现Dinic 的理论复杂度是 O(E * V^2)在一般图上可能到 1e5 级别的边就有点吃力了但这里有个误区实际表现远好于理论值尤其是在分层图较短的情况下。大多数竞赛题目的网络流模型分层长度都很短三四层Dinic 在这个场景下往往是 O(E * sqrt(V)) 级别的表现虽然这不是严格证明但从经验上看非常可靠。如果图特别大、流量特别大可以考虑 ISAP比 Dinic 少一次 BFS 的重建但实现起来细节更多。我自己一般 Dinic 跑不动了才换 ISAP绝大多数情况 Dinic 已经足够。4.3 我踩过的坑和排查技巧第一忘记加反向边。这个错误非常隐蔽因为代码编译不报错、运行也不崩但结果永远是 0。排查方式是打印每条边的残量看反向边是否存在。建议add_edge函数里顺手就把反向边加好不要图省事。第二拆点编号规划错误。当我们拆点后点的数量翻倍边的数量暴涨。比如原图有 n 个点、m 条边拆点后点数是 2n边数大概是 m n中间容量边。开数组时一定要提前算好上限我见过不少人开了N数组结果拆点后最大顶点数变成2*N溢出导致随机 RE运行时错误。第三容量为 0 的边不要加。有些题给的输入里存在容量为 0 的边它们对最大流没有贡献但会在 BFS/DFS 中增加无意义的遍历。我一般直接跳过能省一点常数是一点。第四二分判定时上下边界要开对。如果要用最大流做二分答案判定下界通常是 0但上界要考虑题目中给出的理论极限不要开太大否则二分次数增多而且流量值可能溢出。宁可上界开得恰好一点比如任务总量之和。第五注意 INF 容量的边不要多到让总流量变成 INF。建图时所有正收益之和、总需求这些值都可能超过 int用long long统一能省掉很多麻烦。我在纸上推演时会把 INF 设成一个“足够大但不会溢出”的值比如1e15而不是真的让所有 INF 边都累加起来之后爆掉上限。5. 实战案例串讲一个完整的“判定 拆点 建图”综合题前面四条比较独立现在我来串一个综合案例把“判定”、“拆点”、“建图”三个技巧同时用上。问题背景有 n 个城市m 条有向航线每条航线从 u 到 v每天最多飞行 c 架次客机。现在有 k 个航班任务每个任务从某城市到某城市每天执行若干次而每个城市每天最多允许起降 p_i 架次起降合计。问能否安排所有任务正常执行这个题第一眼看起来像是“多个航班到多个目的地”我们可以这样建模每个城市 i 拆成入点 i_in 和出点 i_out容量为 p_i表示这个城市一天内总的起降容量。每个航班任务从城市 A 到城市 B连一条 A_out 到 B_in 的边容量为需求次数。注意这里 A_out 到 A_in 不需要连因为起降容量由中间容量边统一控制。超级源 S 连每个任务的起点城市的出点容量为任务次数终点城市的入点连超级汇 T容量为任务次数。对城市起降容量 p_i 的限制体现在 i_in 到 i_out 的边上这样所有经过该城市的流量都会被这个容量卡一下。跑一遍最大流看看流值是否等于所有任务需求总和。等于则可安排小于则说明容量不够。这里“判定”就是“流值等于目标值”拆点就是处理城市起降容量建图就是讲清楚任务和航线的方向关系。这个案例我建议新手亲手画一遍图把编号标清楚整个过程不超过 20 分钟但对理解拆点、超级源汇、判定这三件事的组合有奇效。再做一步延伸如果任务可以拆分成不同航班比如 A 到 C 可以经停 B那就把航线当成边、城市拆点当成点一个多层的“中转网络”就出来了。这也是网络流相对其他算法最舒服的地方——逻辑上的约束映射到图上的结构几乎是一一对应的改动起来也很直观。6. 训练建议与场景拓展6.1 从“会模板”到“会建图”的练习路径我自己的体验是最大流入门最难的坎不是写 Dinic而是拿到一道题不知道建什么图。这个唯有靠刻意练习。我建议的练习路径是先把标准最大流、二分图最大匹配、最小路径覆盖这三类基础题目各刷 3~5 道做到不看板子能手写。把所有用“拆点”的题集中刷一遍总结规律什么时候拆点拆完之后原图的出入边怎么连再练“判定”类二分答案 最大流判定的套题。最后挑战综合题既有拆点又有判定又有分层图的复杂题。每个阶段做完写一页纸的小结用自己的话描述“我为什么这样建图”这对建立长时记忆特别有效。6.2 网络流在非竞赛场景的真实应用很多人觉得网络流只是竞赛题其实它在现实中也很常见物流调度、交通流量控制、分布式计算的任务分配、电路中的电流分配电流和流量天然同构都能用最大流建模。我曾在某个内部工具里用最大流做过资源分配有多个计算任务需要不同的 GPU 资源每个 GPU 同一时间只能跑一个任务任务之间有依赖顺序。这个问题抽象成网络流之后调度方案一目了然比手写贪心稳定得多。所以就算你不打竞赛花几个月把网络流这一套吃透绝对不亏。它给你提供了一种“从约束视角看问题”的思维框架这在很多工程场景都能复用。最后再分享一点个人体会网络流建图这件事本质上是在“用图表达约束”。你把一个实际问题的所有限制条件一条条列出来再想每条限制对应图里的哪种结构——容量边、点容量、超级源汇、INF 边——图自然就出来了。我刚开始总觉得建图是玄学后来发现它就是“约束翻译”翻译多了自然熟练。踩过几次坑之后我最深的感受是先把问题里的“源、汇、容量、目标”四个要素写出来比急着画图管用十倍。 
长河君 · 2026/10/14 23:01:38 · 阅读 1.2k 最大流判定与拆点建图实战：从网络流模型到Dinic算法
先交代一个背景我刚接触网络流那会儿连“为什么拆点之后原来的边要连到入点从出点连出去”都绕了很久才想通。等到真正动手刷题、写板子才意识到最大流这一章最值钱的部分不是背模板而是会用“判定”的思路去转化问题、会用“拆点”去处理点容量、会把一个陌生问题一点点掰开揉碎变成一张能跑的图。这篇就把我实际用到的三板斧——最大流判定、拆点、建图实战——完整讲透结合题目和代码一起说。1. 先把最大流的模型和“判定”这件事理清楚1.1 标准最大流模型到底在做什么最大流问题看着简单给一个有向图每条边有一个容量上限然后从源点 S 到汇点 T 运输“流量”问最多能运多少。但真正刷题的时候你会发现题目几乎不会直接说“给你一张图求最大流”而是给你一个实际问题让你自己抽象成图。这里要把握住三个约束容量限制每条边的流量不超过容量、流量守恒除源点和汇点外每个点的流入量等于流出量、反对称性从 u 到 v 的流量是正的则从 v 到 u 的流量是负的。所有最大流算法都是在这三个约束下求可行流的最大值而 Dinic、ISAP 这些算法本质上都是在不断寻找增广路把流量逼近最大。有一个很重要的直觉最大流问题的本质是“资源在容量约束下从供给端到需求端的最优分配”。所以调度、匹配、路径规划、电路分析里大量问题都能套进这个框架。1.2 “最大流判定”到底是什么很多人看到“判定”两个字就懵了以为是另一种算法。其实在竞赛和实战里“最大流判定”通常指两类场景。第一类是把判定问题转化为最大流比如给定一些约束条件问“是否存在一种分配方案”这时候我们往往建一个图跑最大流看最大流是否等于某个目标值。最典型的就是二分图最大匹配左侧点连右侧点每个点容量为 1源点连所有左侧点、右侧点连汇点如果最大流等于左侧点的数量就说明所有左侧点都能匹配上这是一个“完美匹配判定”。第二类是让最大流本身去判定某个参数是否可达典型做法是二分答案把“可行性”判定拆成多次最大流。比如我们要找一个最小的时间 T让所有任务都能在 T 内完成那我们可以对 T 二分每次用最大流判定当前 T 下是否存在可行方案。这里要给一个核心结论最大流跑出来的结果不仅仅是一个数它可以作为“可行性判定的裁决器”。只要你能把“可行”等价转换成“存在一个流使得某个值达到 X”那么最大流就是你的判定函数。这个思维方式比写模板重要得多。1.3 判定问题的通用构图套路我自己的习惯是先回答三个问题再动手建图谁是源谁是汇——源代表供给汇代表需求。什么限制是“容量”——容量代表资源上限可能是时间、人数、流量。目标是什么——通常是让某个量达到最大或者让某个量等于某个值。举个例子现在有 n 个工作m 台机器每个工作需要某种机器资源每台机器同一时间只能处理一个工作问最多能同时开工多少个工作。这就是个二分匹配判定源点连工作工作连能用的机器机器连汇点所有容量为 1跑最大流结果就是最多能同时开工的工作数。很多看起来不像是“流量”的问题一旦你找到这三个问题的答案图就自动出来了。2. 拆点从“点容量”到“边容量”的转化魔法2.1 拆点要解决什么问题网络流的容量是定义在边上的但有一类问题限制的是点比如一个城市节点最多只能通过 C 辆卡车一个服务器节点最多只能处理 D 个请求一个中转站最多只能中转多少货物。这些情况下我们没有办法把“点容量”直接写进标准最大流模型因为算法的增广操作是沿着边走、对边容量做减法它并不知道“点”有容量。解决方案就是拆点把某个节点 i 拆成 i_in入点和 i_out出点然后在这两个点之间连一条容量为点容量的边。这样所有进入原节点 i 的流量必须先流进 i_in再通过那条容量受限于点容量的边到达 i_out才能继续流出。点的限制就变成了中间那条边的容量限制。这个技巧的本质是把一个“点的容量约束”等价转化成一个“边的容量约束”让标准算法可以处理。2.2 拆点的标准姿势拆点的时候我一般这样操作给每个原节点 i 分配两个编号比如i和i n假设原图有 n 个节点。从i入点到i n出点连一条容量为c_i的边——这就是点容量。原图中所有从 u 到 v 的边改造为从u nu 的出点连到vv 的入点的边容量不变。连接关系很好记“入边连入点、出边从出点出、中间边管容量”。如果点本身没有容量限制中间那条边的容量设为INF也行这样它不会成为瓶颈。注意一个坑如果你把中间点容量边设成 0等于这个点完全不可用设成 INF等于没有点容量限制。但千万别漏掉这条边否则入点和出点之间是断开的流量根本出不去。我第一次做拆点时就在这上栽了跟头。2.3 拆点的经典场景分层图与路径限制拆点不只是用来处理点容量的它还能处理更复杂的结构。一个常见场景是“不允许经过同一个节点两次”的路径问题。比如问一条从 S 到 T 的路径最多能经过多少不同的点或者求 S 到 T 的不相交路径数。这时候我们拆点让除源和汇以外的每个节点中间容量为 1那么一条增广路就相当于一条路径中间容量为 1 意味着这条路径不能重复使用同一个节点。跑最大流得到的结果就是最多能找到多少条节点不相交的路径。另一个是“分层图”思路当流量带有时间维度比如在 t 时刻到达某个节点我们可以把每个节点按时间拆成多层每层代表一个状态。虽然这不完全是传统拆点但核心思想一致——多个状态或者多个限制维度就用拆点/分层把它展开到图上。2.4 拆点与费用流、最小割的联动拆点也不仅限于最大流。在费用流里面如果每个节点有一个“处理成本”或“处理上限”同样可以拆点在入点和出点之间连一条带费用的容量边每单位流量经过该点就要付出对应的费用。而在最小割问题里拆点能用来表达“删除一个节点的代价”把节点拆成入点出点中间边的容量就是删除这个节点的代价割掉这条边就等价于删除这个节点。记住一句话拆点把“节点”的语义变成“边”的语义一旦变成了边容量、费用、割代价都可以往上挂。这是拆点最大的价值——不是解决某个具体问题而是统一地把一类问题纳入网络流的可处理范围。3. 建图实战四个经典问题的手把手建模这一节是重头戏我不讲虚的直接上四个实战场景从易到难每个都给出完整的建图思路、容量设定、以及为什么这样建。3.1 二分图最大匹配与完美匹配判定问题背景有 n 个求职者和 m 个岗位每个求职者能胜任其中若干岗位一个岗位只能招一个人问最多能安排多少人上岗。建图方案建超级源点 S超级汇点 T。从 S 向每个求职者 i 连一条容量为 1 的边。从每个岗位 j 向 T 连一条容量为 1 的边。如果求职者 i 能胜任岗位 j从 i 向 j 连一条容量为 1 的边这里不用拆点因为人和岗位都天然带点容量 1且没有中间传递。跑一遍最大流流量大小就是最多能安排的人数。如果最大流等于 n说明所有求职者都能安排到岗位这就是“完美匹配判定”。这里有一点值得展开为什么用最大流而不是直接贪心匹配因为二分图匹配有一个“重新分配”的过程贪心会陷入局部最优而最大流的增广路机制天然允许反悔。这也是 Dinic 比朴素的贪心匹配更稳妥的原因。3.2 带节点容量的一般网络最大流问题背景一张有向图除了边有容量每个中转节点非源非汇最多只能通过 C_i 的流量求源到汇的最大流。这个问题的场景非常常见比如一个物流网络每个仓库有吞吐上限。建图方案就是在普通图上加拆点把所有中间节点 i 拆成 i_in 和 i_out。i_in 到 i_out 连容量为 C_i 的边。原图中边 u - v容量 cap改造为 u_out - v_in容量 cap。源点 S 可能没有入度但仍把它拆成 S_in 和 S_out或者直接用 S_out 作为源汇点 T 同理用 T_in 作为汇。跑最大流结果就是全局最大流量。我建议在做这类题时先画一张改造前后的图对比一下改造前是“点重叠”“边相连”改造后变成了“点拆开”“边串过”。画一遍之后对拆点的理解会彻底稳固。3.3 有向无环图的最小路径覆盖问题背景给定一个 DAG问最少需要多少条路径路径间不能相交即不能共用节点才能覆盖所有节点。这个问题的答案是节点数 - 最大匹配数。这个结论看起来是从图论里来的但它的证明和实现都依赖网络流/二分图匹配。建图方案把每个节点 i 拆成左点 i出点和右点 i入点形成一个二分图。如果原图有边 u - v则在左点 u 和右点 v 之间连一条容量为 1 的边。超级源 S 连所有左点容量 1所有右点连超级汇 T容量 1。跑最大流得到最大匹配数最小路径覆盖数 n - maxflow。为什么是这个公式直观理解一开始每个点都是一条单独的路径总共 n 条。每匹配一对 u-v就相当于把“以 u 结尾的路径”和“以 v 开头的路径”拼接起来路径总数减 1。拼接不能重复用节点所以每个左点、右点都只允许匹配一次容量为 1 正好满足。3.4 多源多汇与超级源汇的合并问题背景有时候源点和汇点不是单一的一个而是多个。比如有 3 个仓库、5 个销售点要给每个销售点送货。我们不可能把最大流算法扩展到多源多汇算法要求的是一对一源汇最然存在变体但最稳妥的方式是合并最简单的做法是加一个超级源和超级汇。建图方案新增 S* 和 T*。S* 向每个原有仓库源点连一条容量为对应仓库供货能力的边。每个原有销售点汇点向 T* 连一条容量为对应销售点需求量的边。原始图中源和汇的语义就消失了统一变成了普通节点整个图变成一个单一源汇的最大流网络。这里有个技巧如果某个销售点的需求量是 D连 D 容量如果仓库供货能力不确定连 INF。跑完后流量就是总供货量。如果要判定“能否满足所有需求”就看 maxflow 是否等于所有需求之和。3.5 最大权闭合子图拆点延伸到最小割这个问题稍微偏最小割一点点但在建图实战里非常经典。问题背景有 n 个项目每个项目有收益可能为正也可能为负项目之间有依赖关系做项目 A 必须先做项目 B选一些项目使得总收益最大。这个问题用最大流等效于最小割解决。建图方案对于收益为正的项目 i从 S 向 i 连容量为收益的边。对于收益为负的项目 j从 j 向 T 连容量为 -收益即代价的边。依赖关系 u 必须先于 v从 u 向 v 连一条容量为 INF 的边。答案 所有正收益之和 - 最小割即最大流。割的含义割掉 S 到正收益的边表示放弃这个项目割掉负收益到 T 的边表示承担这个项目的成本。INF 边保证依赖不会被破坏。这也是为什么“最大流 最小割”这个对偶关系在实战中极其重要——有些问题适合从“最大流”角度想有些适合从“最小割”角度想但代码上跑的是同一个算法。4. Dinic 板子、复杂度与避坑清单4.1 一份带注释的 Dinic 实现网上板子很多但很多对新手不友好我贴上我自己一直在用的版本加了比较详细的注释#include bits/stdc.h using namespace std; const int N 1005; const long long INF 1e18; struct Edge { int to; // 边的终点 long long cap; // 剩余容量残量 int rev; // 反向边在邻接表中的下标 }; vectorEdge g[N]; int level[N], iter[N]; // level: BFS分层 iter: 当前弧优化指针 void add_edge(int u, int v, long long cap) { // 正向边 g[u].push_back({v, cap, (int)g[v].size()}); // 反向边初始容量为 0 g[v].push_back({u, 0, (int)g[u].size() - 1}); } // BFS 构建分层图返回是否能从 s 到达 t 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 (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] ! -1; } // DFS 在分层图中寻找增广路返回实际增广的流量 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[u] level[e.to]) { 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 max_flow(int s, int t) { long long flow 0; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); while (true) { long long f dfs(s, t, INF); if (f 0) break; flow f; } } return flow; }这个板子的几个细节值得注意反向边容量等于正向边已经使用的流量这是匈牙利增广的一种形式化给算法提供“反悔”能力。level[u] level[e.to]是保证 DFS 只在分层图上沿着层数递增的方向走防止死循环。iter[u]是当前弧优化代表从 u 出发的边里哪些已经用尽了残量为 0下次直接从下一条开始避免重复遍历已经没有流量的边。INF设成1e18并且用long long是因为网络流题目里容量经常给到 1e9若干条边叠加后可能会超过 int 上限。4.2 时间复杂度和实际表现Dinic 的理论复杂度是 O(E * V^2)在一般图上可能到 1e5 级别的边就有点吃力了但这里有个误区实际表现远好于理论值尤其是在分层图较短的情况下。大多数竞赛题目的网络流模型分层长度都很短三四层Dinic 在这个场景下往往是 O(E * sqrt(V)) 级别的表现虽然这不是严格证明但从经验上看非常可靠。如果图特别大、流量特别大可以考虑 ISAP比 Dinic 少一次 BFS 的重建但实现起来细节更多。我自己一般 Dinic 跑不动了才换 ISAP绝大多数情况 Dinic 已经足够。4.3 我踩过的坑和排查技巧第一忘记加反向边。这个错误非常隐蔽因为代码编译不报错、运行也不崩但结果永远是 0。排查方式是打印每条边的残量看反向边是否存在。建议add_edge函数里顺手就把反向边加好不要图省事。第二拆点编号规划错误。当我们拆点后点的数量翻倍边的数量暴涨。比如原图有 n 个点、m 条边拆点后点数是 2n边数大概是 m n中间容量边。开数组时一定要提前算好上限我见过不少人开了N数组结果拆点后最大顶点数变成2*N溢出导致随机 RE运行时错误。第三容量为 0 的边不要加。有些题给的输入里存在容量为 0 的边它们对最大流没有贡献但会在 BFS/DFS 中增加无意义的遍历。我一般直接跳过能省一点常数是一点。第四二分判定时上下边界要开对。如果要用最大流做二分答案判定下界通常是 0但上界要考虑题目中给出的理论极限不要开太大否则二分次数增多而且流量值可能溢出。宁可上界开得恰好一点比如任务总量之和。第五注意 INF 容量的边不要多到让总流量变成 INF。建图时所有正收益之和、总需求这些值都可能超过 int用long long统一能省掉很多麻烦。我在纸上推演时会把 INF 设成一个“足够大但不会溢出”的值比如1e15而不是真的让所有 INF 边都累加起来之后爆掉上限。5. 实战案例串讲一个完整的“判定 拆点 建图”综合题前面四条比较独立现在我来串一个综合案例把“判定”、“拆点”、“建图”三个技巧同时用上。问题背景有 n 个城市m 条有向航线每条航线从 u 到 v每天最多飞行 c 架次客机。现在有 k 个航班任务每个任务从某城市到某城市每天执行若干次而每个城市每天最多允许起降 p_i 架次起降合计。问能否安排所有任务正常执行这个题第一眼看起来像是“多个航班到多个目的地”我们可以这样建模每个城市 i 拆成入点 i_in 和出点 i_out容量为 p_i表示这个城市一天内总的起降容量。每个航班任务从城市 A 到城市 B连一条 A_out 到 B_in 的边容量为需求次数。注意这里 A_out 到 A_in 不需要连因为起降容量由中间容量边统一控制。超级源 S 连每个任务的起点城市的出点容量为任务次数终点城市的入点连超级汇 T容量为任务次数。对城市起降容量 p_i 的限制体现在 i_in 到 i_out 的边上这样所有经过该城市的流量都会被这个容量卡一下。跑一遍最大流看看流值是否等于所有任务需求总和。等于则可安排小于则说明容量不够。这里“判定”就是“流值等于目标值”拆点就是处理城市起降容量建图就是讲清楚任务和航线的方向关系。这个案例我建议新手亲手画一遍图把编号标清楚整个过程不超过 20 分钟但对理解拆点、超级源汇、判定这三件事的组合有奇效。再做一步延伸如果任务可以拆分成不同航班比如 A 到 C 可以经停 B那就把航线当成边、城市拆点当成点一个多层的“中转网络”就出来了。这也是网络流相对其他算法最舒服的地方——逻辑上的约束映射到图上的结构几乎是一一对应的改动起来也很直观。6. 训练建议与场景拓展6.1 从“会模板”到“会建图”的练习路径我自己的体验是最大流入门最难的坎不是写 Dinic而是拿到一道题不知道建什么图。这个唯有靠刻意练习。我建议的练习路径是先把标准最大流、二分图最大匹配、最小路径覆盖这三类基础题目各刷 3~5 道做到不看板子能手写。把所有用“拆点”的题集中刷一遍总结规律什么时候拆点拆完之后原图的出入边怎么连再练“判定”类二分答案 最大流判定的套题。最后挑战综合题既有拆点又有判定又有分层图的复杂题。每个阶段做完写一页纸的小结用自己的话描述“我为什么这样建图”这对建立长时记忆特别有效。6.2 网络流在非竞赛场景的真实应用很多人觉得网络流只是竞赛题其实它在现实中也很常见物流调度、交通流量控制、分布式计算的任务分配、电路中的电流分配电流和流量天然同构都能用最大流建模。我曾在某个内部工具里用最大流做过资源分配有多个计算任务需要不同的 GPU 资源每个 GPU 同一时间只能跑一个任务任务之间有依赖顺序。这个问题抽象成网络流之后调度方案一目了然比手写贪心稳定得多。所以就算你不打竞赛花几个月把网络流这一套吃透绝对不亏。它给你提供了一种“从约束视角看问题”的思维框架这在很多工程场景都能复用。最后再分享一点个人体会网络流建图这件事本质上是在“用图表达约束”。你把一个实际问题的所有限制条件一条条列出来再想每条限制对应图里的哪种结构——容量边、点容量、超级源汇、INF 边——图自然就出来了。我刚开始总觉得建图是玄学后来发现它就是“约束翻译”翻译多了自然熟练。踩过几次坑之后我最深的感受是先把问题里的“源、汇、容量、目标”四个要素写出来比急着画图管用十倍。