最大流建模实战：拆点与二分答案判定技巧解析

网络流这块内容说难也难说简单也简单。难在建模——你永远不知道题目里那个花里胡哨的场景怎么就会变成一张带容量的有向图。简单也在建模——一旦你从题目描述里嗅出流量分配的味道把源点、汇点、容量对号入座剩下的就是套模板跑Dinic。今天这篇就围绕最大流的判定、拆点和建图实战把我在各种题目里踩过的坑和总结出来的套路一次性讲清楚。适合刚学完网络流模板、想往上突破建模能力的同学也适合那些把Dinic背得滚瓜烂熟、但一拿到新题就不知道从哪下手的选手。1. 先搞明白最大流在解决什么问题1.1 最大流的本质是一张带容量限制的运输网我们抛开数学定义用最直观的方式理解。假设有一座自来水厂源点就是水厂汇点就是你家水龙头中间是一张由水管组成的城市管网。每根水管有个粗细也就是容量代表单位时间最多能通过多少水。网络流要回答的问题是单位时间内你家里最多能接到多少水这就是最大流。任何能在图上抽象成从起点运输资源到终点每条边有运输上限的问题几乎都能用最大流解决。比如二分图最大匹配每个人只能选一个岗位每个岗位只能招一个人有向无环图的最小路径覆盖最少用几条路径能覆盖所有点任务分配若干任务分给若干工人每个工人有工作时间限制赶工问题给定工期判断所有任务能否完成你发现没有这些看似完全不同的题型底子都是同一个东西资源从一组节点流向另一组节点每个节点或每条边有容量约束目标是让总流量最大或者给定流量问能不能达到。1.2 一道题该不该用最大流怎么迅速判断我自己的判断标准很简单就三条题目能分成供应方和需求方两个集合资源从一边流向另一边。存在明确的容量约束比如数量不超过次数至多容量为最多容纳。问的是最多能完成多少能否完成所有最少用多少条路径。只要同时满足大概率就是网络流题。如果题目还出现了每个点最多经过一次每个点有容量限制这种话那大概率还要配合拆点。很多同学卡在第一步读完题感觉像网络流又觉得像贪心或者像DP犹豫来犹豫去。我的建议是碰到带最多、最少、是否可行且带数目约束的题先用网络流方向想十分钟。如果建图思路通畅直接干如果十分钟还没思路再考虑其他算法。这不是效率低这是算法竞赛里最常见的有思路就跑没思路及时换赛道策略。1.3 Dinic算法快速回顾模板背熟然后忘掉它建图再漂亮跑不出来也白搭。目前最常用的最大流算法就是Dinic复杂度理论上界是O(V²E)实际跑起来远快于这个值对付绝大多数信息学竞赛题够了。这里快速过一遍结构后面实战部分不重复解释。struct Edge { int to, cap, rev; // 目标点剩余容量反向边在邻接表中的下标 }; vectorEdge G[MAXN]; int level[MAXN], iter[MAXN]; void addEdge(int from, int to, int cap) { G[from].push_back({to, cap, (int)G[to].size()}); G[to].push_back({from, 0, (int)G[from].size() - 1}); } void bfs(int s) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int v q.front(); q.pop(); for (auto e : G[v]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[v] 1; q.push(e.to); } } } } int dfs(int v, int t, int f) { if (v t) return f; for (int i iter[v]; i (int)G[v].size(); i) { Edge e G[v][i]; if (e.cap 0 level[v] level[e.to]) { int 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; } int maxFlow(int s, int t) { int flow 0; while (true) { bfs(s); if (level[t] 0) return flow; memset(iter, 0, sizeof(iter)); int f; while ((f dfs(s, t, INF)) 0) { flow f; } } }注意第2行我把边存成了结构体比存两个平行数组更直观。第13行的level[v] level[e.to]是关键它保证了dfs只在分层图上跑不会绕圈。2. 最大流判定判断能不能达到某个流量2.1 判定问题的本质是可行性不是最优化很多网络流题目跑一遍最大流算出流量值这只是一半。真正有区分度的考点在判定给定一个目标流量F问能不能达到或者换个问法当前方案是否满足所有约束这就像你打车到机场最大流告诉你最多能跑多少趟而判定问题是老板拍板说今天必须送完F趟你要判断行不行。跑出来的最大流maxFlow如果大于等于F就行小于F就不行。这听起来像废话但妙就妙在很多题不是直接给你一个F而是要你求一个最优的F。2.2 二分答案 最大流判定最常见的高频套路举一个我做过很多次的题型有n个任务和m个工人每个任务必须在某个时间窗口内完成每个工人同一时间只能做一个任务问最少需要多少天能完成所有任务。这里最少需要多少天不好直接求但如果我告诉你天数K你能不能判断是否可行呢当然可以把所有任务在K天内能否完成变成一张流网络跑最大流看最大流是否等于任务总数。等于就说明K天够了不等于就说明不够。于是整个解法就成了二分答案K天数。对每个K建一张任务—工人—时间的流网络跑最大流。如果最大流等于任务数说明K可行二分搜索右边界向左收否则说明K不够左边界向右推。这种把最优化问题转成判定问题再用二分枚举答案去逼近最优解的方法在网络流题目里出现频率极高号称网络流里的二分图国王也不过分。建图部分长这样bool check(int K) { // 建图源点向每个任务连边容量为1 // 每个任务向能完成它的每个时间槽连边容量为1 // 每个时间槽向汇点连边容量为1一个槽只能被一个任务占用 // 跑最大流判断是否等于任务总数 }这里面有个细节容易出错二分判定里的建图必须是干净的每次check都要重新建图不能上一次的残留网络影响下一次。我见过不少同学在循环里忘了清空图导致判定结果一直被上一次的流量污染调一晚上都没发现。2.3 判定题的另一个变种至少要几条路径/几次操作除了二分答案判定题还有一个常见变种就是可行性检查本身藏在别的算法里。比如最小路径覆盖问题最后判断顶点数减最大流是否等于目标值再比如混合图欧拉回路要判断调整后的每条边能否平衡入度出度。这类题的特征是最大流跑出来的值直接参与比较比较结果决定输出Yes或No。这里我单独提醒一句判定类网络流题写完最大流之后千万别急着交一定要单独验证建图代码里容量有没有写反。源点出发的边容量给大了汇点入边容量给小了最后算出来的流量会非常离谱而且样例往往恰好能过。我自己就有过惨痛教训在某次模拟赛里二分答案的judge函数写错了一条边容量小样例全对一到大数据就错废了我整整一个下午。3. 拆点解决点也有容量限制的标准操作3.1 为什么点也要拆边有容量的反直觉情况网络流的基础模型里只有边有容量点没有。但真实的约束里点往往比边更金贵。比如每个路口最多通过X辆车每个城市最多停留一次每个人最多被分配到Y个任务——这些都是点的约束。把点约束转到边约束靠的就是拆点。操作上很无脑把一个点v拆成两个点v_in和v_out中间连一条边容量等于这个点的容量。所有原来指向v的边改成指向v_in所有原来从v指出的边改成从v_out出发。这样点容量就被转移到了内部边上。// 拆点v_in 编号为 v*2v_out 编号为 v*21 addEdge(v_in, v_out, pointCapacity); // 原边 u - v容量c改为 addEdge(u_out, v_in, c);这个操作解决了一个本质问题最大流算法只会尊重边的容量如果点不拆再好的建模也无法体现这个点总共只能流过去多少流量。拆点相当于把点的约束翻译成了算法听得懂的语言。3.2 入点和出点两条原则别搞混拆点之后图的拓扑会发生一些微妙变化有两个地方新手极易出错。第一个是方向性问题。从源点出发的边目标应该接到被拆点的入点还是出点取决于这条边在语义上是进入这个点还是从这个点出来。简单记入边进in出边离out。中间那条in到out的边代表点本身对容量的消耗。第二个是编号问题。拆点之后节点数量直接翻倍所有数组和邻接表的大小要开够。我见过好几次RE不是算法错了是数组只开到原来的大小拆完点一访问就炸。我习惯的拆点编号方案是以2为倍率点的编号从1开始v_in v * 2v_out v * 2 1。这样还有个附加好处判断一个节点是in还是out直接看奇偶就行。调试的时候这个性质很管用你会在控制台里飞快地定位到是哪个点出了问题。3.3 拆点的两个变式费用优先和点不可重复拆点不是只会拆成两个点根据题意可以玩出花来。变式一带费用/每点经过多次的拆法。如果一个点最多能被经过C次但每经过一次要消耗费用那么中间那条in→out的边可以拆成两条一条容量为1、费用为cost另一条容量为C-1、费用为0。这样第一次经过付费后续经过免费。这个套路在最小费用最大流里尤其常见最大流题目偶尔也会出现类似的需求。变式二路径覆盖类问题的拆法。最小路径覆盖问题里每个点恰好被覆盖一次拆法是把一个点拆成链起点和链终点两个角色连边方向有些不同。这个下面实战部分会细讲这里先记住一个核心思想拆点拆的是角色的分离同一个点在不同时刻扮演不同角色时就需要拆成不同的点。拆点这个操作本身不难难的是判断这里要不要拆。我总结了一个判断口诀题目描述中出现每个点最多……或每个点恰好……且这个点不在源点和汇点上就考虑拆。如果连这个都没有别乱拆拆了反而会增加不存在的约束把正确答案卡掉。4. 建图实战三类高频题型的建模完整拆解4.1 二分图最大匹配超源超汇的标准搭法二分图匹配是最基础的网络流建图题也是理解后面所有复杂题型的起点。左部有n个点右部有m个点给定若干条左点可以匹配右点的边问最多能匹配多少对。建图过程分三步// 1. 建超级源点s编号0 // 2. 超级源点到每个左部节点连边容量1 // 3. 左部节点到可匹配的右部节点连边容量1 // 4. 每个右部节点到超级汇点t连边容量1跑出来的最大流就是最大匹配数。为什么每边容量都是1因为每个左点最多匹配一个右点每个右点最多被一个左点匹配。这里有一个许多教程不会讲的升华超源和超汇的本质作用是把多个起点和多个终点统一成一个唯一的起点和终点。任何网络流都要求有且仅有一个源点和一个汇点当你发现题目里有很多个供应方和很多个需求方时就用一个超级源点连接所有供应方所有需求方连接超级汇点。这个模式是所有复杂建图的底座。4.2 最小路径覆盖拆点后左右交替的经典构图给一个有向无环图问最少用多少条路径能覆盖所有点每个点恰好被覆盖一次。答案是顶点数减去做完二分图匹配后得到的最大匹配数。建图方式很特别需要对原图每个点v拆成两个点v和v然后按这个规则连边// 设原图节点数为N for (int i 1; i N; i) { addEdge(s, i, 1); // 源点连到每个起点副本 addEdge(i N, t, 1); // 每个终点副本连到汇点 } // 对原图每条有向边 u - v addEdge(u, v N, 1); // 从u的起点副本指向v的终点副本跑一遍最大流N - maxFlow就是最少路径数。背后的直觉是一条路径每经过一条边就相当于把两个点拼在一起相当于省了一次重新开始路径的机会。最大流求出的最大匹配数就是最多能省掉多少次独立路径的起点。这个题如果不拆点完全没法做因为没有边能表示点与点之间拼接成功这件事。我当年学这个题的时候死活理解不了为什么要拆成两个方向。后来自己做了一遍模拟才明白左边那一排点代表路径中的起点或中间点右边那一排点代表路径中的终点或中间点一条边从左边u连到右边v表示u到v在原图中有一条边且v可以作为u的后续点。每个点只能当一个后续点所以右边点连到汇点容量为1每个点最多只能有一个前驱所以源点连向左边点容量为1。这个视角现在回想起来其实就是把选边拼接问题转化成了匹配问题。4.3 时间轴拆点用状态替代时间解决动态排程题有一类题乍看不是图论有若干订单每个订单有若干工序每个工序占用不同机器问能否在期限内全部完成。这种题的建图思路是给时间分层。把整个工期K天拆成K个时间槽每个槽能容纳一台机器运行一个工序。订单、工序、机器、时间槽之间的关系全部用容量1的边连起来。具体建图// 源点 s - 每个订单容量为该订单的工序数 // 订单 - 可执行该工序的机器容量1 // 机器 - 每天的时间槽容量1 // 时间槽 - 汇点 t容量1 // 总流量是否等于总工序数决定K是否可行这里的核心思想是用拆时间把一维的时间约束拍扁成图上节点。时间槽数量K是二分答案枚举出来的K越大能同时执行的工序就越多最大流也更容易达到目标值。这种题我第一次做的时候觉得特别抽象明明是一个排程问题怎么就成了最大流后来想通了排程的本质就是在正确的时间槽里把正确的资源分配给正确的任务而这个分配过程里每一种约束的表单都对应一种容量为1的边。一旦接受了这个设定再看这类题建模思路就非常自然了。4.4 建图前必须做的一步画供需关系图讲了这么多模型我想强调一个方法论层面的技巧。真正动手写建图代码之前先拿草稿纸画一张供需关系图不是画的拓扑结构图而是把题目要素分成三列供应方源侧中间环节需求方汇侧任务工件人钱工序机器路径状态时间槽岗位最终目标然后问自己三个问题供应方和需求方之间的资源流向是单程的还是可逆的每个中间环节有没有容量上限每一条边的容量该给多少这张表画完建图代码写起来就顺水推舟了。很多同学对着题目发呆觉得无从下手其实是没有做这一步抽象。相信我任何一道网络流题只要能把供需关系说清楚图基本就建出来了一半。5. 我踩过的最大流实战坑建图之外的排障经验5.1 INF取值太大溢出太小出错写最大流的人都要面对一个灵魂拷问INF到底取多少我见过有人取0x3f3f3f3f也就是约10亿出头这个值在int范围内手算也好打印也好都很方便。但在某些大数据题目里总流量可能超过21亿比如有10万个点、每条边容量上限是10万最大流轻松超过int上限。这时候如果还按int做直接溢出变负数代码永远跑不出去。我的建议是只要题目给的范围没有明确说总流量在int范围内一律用 long long。const long long INF 1LL 60;取一个足够大的数既能保证所有边的容量相加不会溢出又不会导致算法里min(f, e.cap)出错。还有个细节addEdge里的cap参数类型也要跟着改不然中间一截窄化转换照样溢出。5.2 反向边不是摆设写挂最多的地方Dinic模板里addEdge要同时插一条容量为0的反向边。这个反向边承载了两个救命功能允许算法在增广过程中退回去已分配的流量从而找到更优的全局方案。记录每次增广实际流过的量用于流量统计。新手最容易犯的错误有两个一是忘了插反向边结果图直接变成单向链算出来的流量永远偏小二是在dfs里更新剩余容量时写反改的是反向边的容量正向边反而没动导致流越来越多。我自己调试的时候靠一个必杀技定位这种bug跑完最大流后把所有正向边的cap加起来看是否等于算出来的flow。如果对不上八成是更新方向写反了。5.3 拆点编号错乱数组越界的元凶拆点之后节点数翻倍最容易出现的运行错误就是数组越界。我曾经在一个拆点加二分答案的题里数组开的MAXN5000但实际拆点后节点编号到了8000程序随机RE排查了很久才发现是数组开小了。这里我给一个非常实用的建议拆点编号的偏移量写成一个全局常量比如const int OFF N 5;然后用v OFF表示出点而不是手写在v*2这类算式里到处飘。这样即使后面改点数只需改一个常量不会漏改哪个地方。另外调试拆点题时有个小技巧把所有节点的in和out编号打印出来对着自己的建图草稿核对一遍基本能秒杀所有编号型错误。5.4 TLE的排查别一上来就怪算法跑Dinic超时先别急着怀疑算法本身。按照下面这个顺序排查通常比你折腾模板快得多是不是每次二分判定都在重复建图但没清空旧图这是最常见的TLE元凶本来O(logK)次建图你的代码变成了O(logK)次建不完的图。是不是邻接表里塞了太多无效边有些同学建模时把所有可能边都加一遍实际上很多边永远不会被用到白白增加dfs的开销。是不是死循环Dinic里dfs递归深度如果超过系统栈限制会栈溢出崩溃如果level分层逻辑写错可能反复增广永远无法终止。用样例调的时候加一个flow打印看它每次增量是收敛还是跳动。排掉上面这些才轮到优化算法。Dinic的实际表现通常远好于理论上界如果图本身建得干净很少会卡。最后分享一个我养成的小习惯写网络流题这几年我最深的体会是建图错误比算法错误难找十倍。算法错了会RE、会TLE、会答案错但建图错了可能样例全过、大数据全挂连个报错都不给你。所以我现在每道网络流题写完建图之后都会干一件事——用代码把每种节点和边的数量打印出来对着题面逐条验算一遍约束。比如题目说每个点最多经过一次我就去验证拆点后每个点的入边容量和出边容量是否都不超过1题目说总共要分配5件货物我就去验证源点出发的5条容量为1的边是否都连到了正确位置。这个过程有时比跑最大流本身还花时间但几乎每次都能抓出一两个隐形bug。久而久之我的最大流题从碰运气变成了稳如老狗。网络流这个东西模板只是入门建图思路才是真正的分水岭。多刷不同类型的建模题多总结每类题的“供需关系表”慢慢地你也会形成自己的直觉看到最多覆盖分配这些词脑子里自动浮现一张源点发源、中间拆点、汇点汇聚的图。这条路没有捷径但方向对了每一步都是往前走。