新网络流 24 题， 练后感

Drind · 2024-03-17 16:43:27 · 算法·理论

前言

这个题单真是满满的心血啊。但是就算这样也有一车网络流好题没有被包括进去，比如大家熟知的无限之环，80 人环游世界（哦上下界的题好像就只有一个板子），小园丁与老司机（这个题原本是有的，被我删了，因为我不想写），或者近年来的学术社区（原本想加的，结果死活调不出来，而且这题的难点在于输出方案，而不是网络流）。但是就算这样，我觉得这个题单还是很有练习意义的！！！！

把题单贴在这儿吧。新网络流 24 题

题解

既然要写练后感，那就先把每个题的题解讲一遍吧。需要代码可以看我提交记录，我应该是开了代码公开的，或者私信问我也行。

P2756 飞行员配对方案问题

原 24 的题啊，因为太经典了所以加进来。

我们发现这其实就是一个二分图最大匹配问题，将英国飞行员作为左部点，外籍飞行员作为右部点，能匹配的就在中间连边，然后源点连向左部点，右部点连向汇点就完成了。

输出方案的话，我们枚举中间连的每个边，如果被流过了，就说明这个边的两个端点匹配了，输出即可。

复杂度 n^2\sqrt n，可以通过。

P1251 餐巾计划问题

还是原 24 的题啊，但是这题放前边不代表简单哦。

首先我们很显然的思路就是把餐巾当成流量，要怎么保证每天都有 r_i 块毛巾呢？所以对于每天，我们连一条边到汇点，流量为 r_i，因为最小费用最大流算法会优先保证最大流，所以一定会流满。

但是，每天用剩下的脏毛巾怎么办呢？于是我们每天再从源点连一条流量为 r_i 的边，代表今天多了这么多脏毛巾。

坏事儿了，因为这么跑的话，黑心商家就会把脏毛巾供应使用了。所以我们要拆点，每一天拆成入点和出点，脏毛巾进到出点去，新毛巾从入点流走。

剩下的就是两种清洗方案了，我们直接将这天的出点连向若干天后的入点（因为连过去就变成干净毛巾了）。

还有购买新毛巾，我们直接从源点连向入点，加费用即可。

注意每天的入点要连向下一天的入点，因为干净毛巾可以留到下一天再用。

P2764 最小路径覆盖问题

又是原 24 的题啊，我放他是因为我觉得这个东西貌似很重要的样子。

首先我们先构造出一个路径覆盖，我们发现每个点当成一个路径覆盖就挺不错的呀，这时需要 n 个路径，非常不优，需要改进。

如果两个点 u,v 之间有一条 u\to v 的边，是不是就可以把这两个点合并进一个路径里了。如果 v 再到别的点有边，或者别的点到 u 有边，我们还是可以继续合并。

所以我们把这个问题抽象成一个二分图最大匹配问题，每个点拆成入点出点，一条边就是出点连向入点，然后跑一个最大匹配，就是减少的路径数量，答案就是 n-flow。

extend

如果我们把这个问题稍微改一下，变成可相交的最小路径覆盖（也就是最小链覆盖），怎么做？

我们发现这个新问题本质上就是有的路径可以中间断开的最小路径覆盖。既然可以中间断开，那我们预处理每个点能到达哪儿，然后建出一张新图，在这个新图上，对于任意一个点，在图中的其他点要么和他有边，要么他无法到达（也就是传递闭包，如果你知道这个东西的话）。

这个图怎么做出来呢，我们使用 floyd 算法即可解决。然后在这个新图上跑最小路径覆盖即可。

这个东西会在接下来的某个神秘地方出现，敬请期待！

P4043 [AHOI2014/JSOI2014] 支线剧情

上下界科技模板题。

这个题就是一张 DAG 但是每条边都必须走一次，求最小费用可行流。

既然这样，我们就强制把每条边都先存在一个 1 的流量，但是这样整张图的流量就不平衡了对吧！为了平衡流量，我们强制他们流掉，如果多了流量就往汇点连，少流量就往源点连，然后跑最小费用最大流，保证这些加的边流满。记得强制流的边要加上费用。

P1646 [国家集训队] happiness

经典最小割题。

我们考虑让程序把选择文科的人割到源点，选择理科的割到汇点。那么直接源点向每个人连选文科的快乐值，每个人往汇点连理科的快乐值。

对于相邻的俩人，我们建超级点，源点向超级点连一条两人选择文科获得的快乐值，超级点向汇点连一条两人选理科的快乐值。然后超级点向两个人都连一条边，权值为无限大（就是不许你割掉他）。

然后跑一遍最大流，因为最大流等于最小割，答案就是 tot-flow，tot 为所有的快乐值之和。

P2754 [CTSC1999] 家园 / 星际转移问题

好像还是原 24 的题...因为我挺喜欢这题的，所以加进来。

首先我们有一个很 naive 的做法就是对于每个时刻都建出 n 个点，也就是建出一个分层图然后跑最大流。但是我们不知道需要多少天啊！所以我们可以考虑二分答案（但是每次重新建图跑的奇慢）或者一些别的做法。

我们枚举它需要多少天，每次加 n 个点 m 条边，然后在残量网络上跑一遍最大流，如果有一天最大流大于 k 说明这一天就是所需最少天数了。

好像挺水的，如果我再修改题单我可能会把他删了。

P5029 T'ill It's Over

码量大注意。

我们把节数看成流量，然后每个光明程度看成一个点，所以就变成了从 [a_1,a_2] 到 [b_1,b_2] 连 n^2 条边的问题了（注意到前三个操作都弱于第四个，所以我们只处理第四个就行）。那么我们这么做，总边数就有 k^2m 条了（注意是对 k 建图而不是 n，后者只是一个上界。）,我们 n^2m 的 dinic 绝对跑不过去。（虽然 dinic 的复杂度也是个玄学就对啦）

所以我们引入图论中优化建图的方法——线段树优化建图即可。具体地，我们建一棵入树，入树的边是向上的，一棵出树，出树的边是向下的，对于每个区间连接操作，建一个超级点，入树上对应这个区间的若干个点连向超级点，超级点连向出树上对应这个区间的若干的点。就能做到在只连接 \log n 个边的情况下连接两段区间了。如果需要加上界，加费用的话，可以拆超级点。

如果要写当前弧，注意复制 head 数组带来的常数。

CF1009G Allowed Letters

这题跟网络流关系较小，但是我觉得二分图匹配相关定理也是网络流的一部分，就擅自加进来了。

我们发现这题就是二分图完美匹配嘛。既然他要最优我们就直接贪心放再判断，这样要跑 6n 次网络流，绝对会死。

我们掏出二分图完美匹配的 hall 定理:

对于一张二分图 G(X,Y)，X 存在完美匹配当且仅当对于 X 的任意子集 S 都有 Y 中能与之任何一个匹配的子集 T 的大小大于等于 S。

以上是我自己翻的，看着很怪啊，其实就是左边任意选几个点，然后右边跟这几个点中任意一个有边的点的数量大于左边选择点的数量。

有了这个我们就很好判定了。但是枚举 n 个点的子集，无异于找死，对吧。但是我们发现对面的字母集只有六个本质不同点，我们把这六种点合并，容易发现最坏情况下选择的子集一定是要么取满所有同种字母，要么不取。所以子集的个数只剩下 2^6 次了，每位贪心即可，复杂度大概是 O(n)，带个 2^6\times 6 的常数，而且大概率跑不满的。

P3980 [NOI2008] 志愿者招募

单纯形艹过去的选手先下去，线性规划批我们暂时不需要，我们在这里只讲网络流做法。

这次的题很不好搞了，因为一个志愿者要负责一个区间，那就是一个流量要对应多个流量，不好搞。

但是每天对应一个点还是需要的吧！所以我们先把这些点建出来，然后他说一个点要对应好多个点对吧，我们尝试用差分的思路，发现根本行不通，但是这个从 s_i 直接跳到 t_i 的思路是不错的。我们直接把所有的需求取反，这样我们如果满足了所有需求，最大流就是 0（否则就是负数，这个东西可能不是很好理解），现在对于一个从 s_i 直接跳到 t_i 的流量，是不是就跟把这段区间内所有需求加一的效果差不多了？因为我们的网络流算法不能处理负数，所以全部加上一个 inf。

这个讲的好像确实有点抽象，如果看不懂可以私信我。

P7730 [JDWOI-1] 蜀道难

我们看到这种区间操作，结果不降的东西，直接给他差分了就好。就变成了你可以分流量给别人，然后要让所有的变成全正。

差分为正的点放在左边，差分为负的点放在右边，然后容易发现一个操作最多只有 n-l_i 种形式，和 n 同阶，那我们直接暴力建 nm 个边。建出来的是个类似二分图的东西,然后跑一个最小费用最大流就行了。无解就是负的没流满。流量与 n 同阶，复杂度 O(n^3m)。

P2050 [NOI2012] 美食节

有一道叫修车的题是这题的数据弱化版。

我们发现，一个人做倒数第 i 道食物，就会有 i 个人在等他，所以我们把每个人拆成若干个点代表做倒数第 i 个菜的他，然后暴力做二分图匹配就能喜提通过修车而这题挂飞。我们发现这个图有太多无用的厨师点了，所以我们每次增广之后找到匹配上了哪个厨师，把这位厨师的下一个点跑出来就行，这样一共需要跑 \sum p 次费用流。总复杂度为 O(nm\sum p)，足以通过本题。

P3337 [ZJOI2013] 防守战线

刚才在志愿者招募那题被我踹下去的线性规划选手，请你上来给大家讲一下这题。

以下内容摘自 TernaryTree 的题解，已经经过原作者许可。

很显然，我们可以设第 i 个位置建 x_i 个塔，于是把这个题目转化为一个线性规划模型：

一个求 \min 的东西，我们自然而然想到去对偶这个线性规划，于是得到：

这东西是一个线性规划板子，可以直接使用单纯形法去解决掉。

好了停停，我们不是来讲单纯形法的，我们是讲网络流的。

我们发现这个式子本质上就是志愿者招募，但是每天最多只能有 c_i 个志愿者，而且要最大权值，我们怎么建图呢？我们直接模仿志愿者招募的建图方式，就是一点对多点的从 l 连到 r+1，但是这次我们每天确定的是上界而不是下界，那我们直接从 i 到 i+1 连流量为 c_i 的边。为了让这个一点对多点的边能减掉这中间的流量，我们把他掉个方向，就是从 r+1 到 l 连一条费用为 d 的边，流量无限大即可。

注意这个图不是必须要让每个流量都到达汇点，所以把图中每个点都连向汇点即可。

P3749 [六省联考 2017] 寿司餐厅

最大权闭合子图

做这个之前，我们要学一手神奇的东西：最大权闭合子图。

闭合子图是啥呢，就是一个子图，保证子图中任何一个点不能到达子图外的点。

最大权闭合子图就是一个有点权的图中，一个包含点权最大的闭合子图，就是字面意思。

怎么求呢，其实就是把原图建出来，每个边赋无限大权值，然后正权点连源点，负权点连汇点，然后跑最小割，最后用所有正权点总权值减去最小割就是答案了。

解题

这题也差不多，我们把每个 d_{i,j} 建成一个点，如果选了 d_{i,j} 就意味着一定要选 d_{i+1,j} 和 d_{i,j-1}，对于权值中的这个 mx^2，我们容易发现这个东西本质上就是选中了一次，就要加上这个权值，那么我们对于每种寿司再单独开一个点，所有这种寿司的 d_{i,i} 选择了，就意味着必须选这个寿司种类点即可。

P2805 [NOI2009] 植物大战僵尸

跟上一题很像，其实也是最大权闭合子图板子题罢了。但是有个小问题就是会出现植物互相保护的环，那么我们跑一个拓扑排序，把成环的植物删掉即可。

P4486 [BJWC2018] Kakuro

进入黑题范畴了。

这个题我写过题解，我觉得我讲的挺好的，我先贺了。

首先，让我们先构造一个符合 Kakuro 游戏的局面，显然最简单的就是所有格子全是 1，然后限制条件是它限制的格子个数，先把他给的局面修改成这个吧。

但是这样太不好了，因为我们根本没考虑他给的局面，所以这个 naive 的构造需要修改。对于每次修改，我们显然要同时改三个值（格子里的数，左边限制条件和上边的限制条件）。而每次修改只会影响这些东西而不会影响别的。

所以我们建立费用流模型，我们把限制条件当成点，从源点向横向限制条件连边，横向限制条件向竖向限制条件连边，竖向限制条件向汇点连边，这样每条增广路就能同时修改三个值了。

然后我们发现有时候修改是更接近初始条件，而有的修改要离初始条件更远，具体地，每个边能让权值更小的修改次数只有初始条件的数减去 naive 构造中的数的次数。所以我们拿这个次数作为流量连一个费用负的边，然后连一个无限流量，费用正的边。

注意没法改的格子边权设为无限大。

最后跑最小费用可行流即可。

如果费用被设为无限大的边被流过或费用无限小的边没流满即无解。

在程序的具体实现中，最小费用可行流意味着每次 spfa 发现到汇点的最短路大于 0 了就可以退出了（再增广不优）。

P3756 [CQOI2017] 老C的方块

最小割神题啊！

我们发现特殊边很神秘，所以先把特殊边两侧的点染成黑色和白色。

但是这样更神秘了因为只有一半的点有颜色，我们就先全部给成第三个颜色。我们发现所有第三色的点都有一个性质就是他要么和黑点相邻，要么和白点相邻，不会同时挨着黑点和白点。我们把挨着黑点的点染成第四色。

完成了四色染色之后，现在我们观察到每个特殊图形都是有四个不同颜色组成的，而且都包含一组横向相邻的黑白点（因为黑白点中间是特殊边）。

更特殊地，每个由四个不同颜色组成的，包含一组横向相邻的黑白点的图形都是特殊图形。

那我们发现，一条第三色到白色到黑色到第四色的路径一定是一个特殊图形，我们可以考虑最小割了。源点到第三色点的边权是第三色点的权值，第四色点到汇点同理。三色点到白，黑到四色点的两条边在图上原本就相邻，没法割。白色点到黑色点的权值赋成他们的最小值，因为这俩点割一个就行，然后跑一个最小割就做完了。

CF343E Pumping Stations

这是最小割树的题，如果不想学这个算法请跳过这题。我保证整个题单有且仅有一道最小割树。

最小割树

既然这样，我们在这里简要介绍一下最小割树。

首先有一个定理是不管你怎么选两点，形成的最小割最多只会有 n-1 种，我们可以造出一颗树来，具体的建造方法就是分治，每次找两个点 在原图上 跑出最小割，然后分成两部分，分治做。

这样形成的树形结构满足任意两点之间的最小割就是在树上的最小割，也就是路径最小值。但是这棵树貌似不叫最小割树叫等价流树，但是无所谓！因为不需要输出方案所以等价流树也可以用。

这样可以过掉 P4897 【模板】最小割树（Gomory-Hu Tree），强烈推荐先把这题过了再看这道 24 中的题。

解题

我们要尽可能的让树上权值最小的那个边不被经过（因为是求最小值所以经过那个最小的就会被推平了），但是要图中每个点都经过一遍所以这个边必须经过一遍，那就让他只走一遍，就可以分治成左右两侧做，然后就做完了。

P4298 [CTSC2008] 祭祀

接下来你要面对的是神秘图论的神秘力量！

首先我们要介绍一个定理叫做 Dilworth 定理，简单来讲就是一张图的最长反链等于最小（可重）链覆盖（还记得我们说这个东西会在神秘的地方出现吗，就在这儿）。而最长反链就是互相无法到达的最大点集合，所以我们跑最小链覆盖就解决了第一问。但是这题还有两问。

我们看这个题第三问，我们应该对于每个点分别讨论，对于一个点，如果把他的传递闭包上的关联点全部删除，答案减少了 1，说明这个点是可选的（传递闭包上的关联点在他选择之后变得不可选定），否则不可选。

我们看这个题第二问，因为一个点选了，他传递闭包上的关联点就不可选，所以我们贪心的从第三问的答案中选择点，给传递闭包上所有他的关联点染色，然后找下一个未被染色的点即可。

P4249 [WC2007] 剪刀石头布

先从神秘的图论世界出来，我们讲个神秘建模题。

这题就是给竞赛图中的一些边定向，使得最后三元环数量最多。

我们正难则反，考虑算有多少个三元环被破坏了，理论上是要有 \frac{n(n-1)(n-2)}{6} 个三元环的对吧。我们对于一个点，如果他的入度大于 1，说明存在两个点都连向他，所以被破坏了 \frac{in(in-1)}{2} 个三元环。

我们对于每个边建一个点，连向他的两个端点，特殊地，如果这个边初始被定向则只连向那个出点。然后源点连边，边连点，点连汇点。

但是还剩下一个问题，就是点连汇点的边费用是 \frac{flow(flow-1)}{2} 的对吧！我们考虑拆边，拆成费用为 0 到 n-1 的 n 条边，流量均为 1 即可。

P5295 [北京省选集训2019] 图的难题

再来个神秘图论题。

我们猜测一个结论就是这个问题等价于这个图的任何一个导出子图均满足 |E|\le 2|V|-2，其中 |E| 为边数，|V| 为点数。不想看证明可以跳过下面一段。

证明

考虑证明，必要性易证，因为一张不存在环的无向图必定是一个森林，保证 |E|\le |V|-1，将黑白两张图叠加即可。

考虑证明充分性，即证明一张满足条件的无向图一定能构造出一个染色方案。我们找到一个度数最小的点，这个点的度数一定不为 4，否则 |E|\ge2|V|，图不合法。

若度数为 1，我们可以随便把这个边染一个色，显然不成环。若度数为 2，我们给两个边染不同颜色，显然不成环。若度数为 3，我们设这个点为 u，连出的三个点分别为 a,b,c。

我们记一张满图为满足条件且 |E|=2|V|-2 的图。

引理 1：两个点相交的满图的并也是满的。

我们设两张图分别为 G_1=(V_1,E_1),G_2=(V_2,E_2)，记他们的交为 G_3=(V_3,E_3)，因为他们的并合法，所以 |E_1|+|E_2|-|E_3|\le 2(|V_1|+|V_2|-|V_3|)-2，因为 G_1,G_2 为满图，所以 |E_1|+|E_2|\le 2(|V_1|+|V_2|)-4，联立得 |E_3|\ge 2|V_3|-2，又因为交合法，所以 |E_3|\le 2|V_3|-2,即 |E_3| = 2|V_3|-2

引理 2：在 a,b,c 中存在一个点对 (x,y) 满足不同时包含在一个满图中。

反证法。我们将包含 (a,b),(a,c),(b,c) 的三个满图合并，根据引理 1，他们的并也是满图，然后我们把 u 和连接 u 的三条边加入图中，发现不符合条件(|E|=2|V|-1)，和我们的假设不符。

我们开始构造方案，我们找到一个 (x,y) 满足不被满图包含，然后将 u 以及连接 u 的三条边删除，添加一条新边 x,y，显然现在新的图符合条件，构造出新图方案后，将 x,u 和 y,u 加入包含 x,y 的颜色中，剩下的一条边加入另一个颜色，显然无环。

求解

我们将边看做左部点，原图中的点看做右部点，边的权值为 1，点的权值为 -2。显然原图的导出子图为新图的闭合子图，且最大权闭合子图的权值大于 -2 时不符合条件。

但是这样会跑出来一个权值为 0 的闭合子图就是空图。所以我们每次钦定一个点，必须选中他（就是把他的权值赋成 0），然后再跑就行了。

但是这样是 O(n^2\sqrt n) 的，过不去 uoj 的#168. 【UR #11】元旦老人与丛林，所以我们考虑优化。

因为每次换一个点钦定的时候只会改变这个点和上一个点的权值，我们考虑使用退流解决。

我们将目前钦定的点记做 i，我们要把这个点的流量退掉，就从 i 到 s 跑一次最大流，然后退掉这个点的流量，将上一个点的流量加回来，跑从 s 到 t 的最大流即可。

[ARC161F] Everywhere is Sparser than Whole (Judge)

还记得刚才那题的导出子图转换成最大权闭合子图的套路吗，其实这题跟上一题那个套路几乎一样，求最大导出子图密度即可。

但是！有两个导出子图是例外，一个是满图，一个是空图，我们要把这俩全部踢掉。

那么我们钦定第一条边必须选，如果跑出来了一个割掉了左边任意一条边的最小割，说明有一个非满图的导出子图密度大于 D，即不合法（其实如果合法的话，跑出来的一定是满图，所以只要有一条边被割掉就是不合法）。

同理，我们钦定第一条边必须不选，再跑一遍，如果右边有一个边被割掉了，即不合法（因为选了点，而且跑出来权值比空图还大，就意味着存在密度大于等于 D 的导出子图）。

CF1416F Showing Off

很好的建模题。

我们发现这个图会变成一个内向基环树森林，每个点只会向比他权值小的连边，而环的权值总是相同的。

因为权值比较自由啊，所以不成环的点可以直接把权值赋成他和他连接的点之差，那我们就不用管环以外的东西了。

我们找到一些点，他必须成环（也就是周围四个数和他权值都相同），有些点可以成环。

然后我们寻找这个环的性质，用黑白染色可以发现环总是偶环，所以我们直接把他拆成若干个二元环总是没错的。

然后我们就可以直接把一个点连向周围权值跟他相同的点，如果必须成环就加个下界，用上下界科技草过去（但是我没草过，如果你想写可以试一下）。

当然这样很不优美。所以我们换一种思路，先黑白染色，然后黑色的必须成环点连向周围，跑一下二分图最大匹配，然后白色同理，这样复杂度是根号的，能过。

在程序实现上，可以把两张图放在一起流，跑得更快。

[AGC038F] Two Permutations

又是一个最小割神题。

我们发现这个 P 和 Q 会形成若干个环，而且 A 和 B 只有两个取值，分别为 i 和在环上偏移一位。

所以就可以对于每个 i 分类讨论：

当 P_i=Q_i=i 时，A_i=B_i。

当 P_i=Q_i 且 P_i\neq i 时当且仅当一个环偏移一位才能使得 A_i\neq B_i。

当 P_i\neq Q_i 且 P_i=i 时只有 Q 偏移一位才能使得 A_i\neq B_i，反之同理。

当 P_i\neq Q_i 且 P_i\neq i,Q_i\neq i 时，任意一个环偏移一位就能使得 A_i\neq B_i。

所以我们设 P 被割到 S 中表示不偏移，被割到 T 中则为偏移，Q 相反，就可以建模了。

对于第一种情况，不可避免的需要 1 的权值。

对于第二种情况，如果两个所在的环被割到同个集合就不需要权值，连一条权值为 1 的边即可。

对于第三种情况，Q 向 T 连边权值为 1 即可，对于情况三还有对偶情况，同理。

对于第四种情况，即 P 在 S 且 Q 在 T 才能产生权值，则从 P 向 Q 连一条 单向边 即可。

然后跑最小割，答案就是 n-flow。

P4542 [ZJOI2011] 营救皮卡丘

这题很像一个最小链覆盖的模型的样子，但是是不对的，因为他是 k 条路径而且要费用最小，而且还有时间限制。

但是这个最小链覆盖的思路是可取的。我们先跑出传递闭包，但是这个传递闭包比较特殊的地方是 dis_{i,j} 代表从 i 到 j 不经过编号大于 j 的点。

事实证明，我们可以让一个人在原地挂机来确保他能在上一个据点被摧毁的同时到达下一个据点，所以直接用这个传递闭包建图，因为有 k 个人从源点出发所以源点连 0 号节点流量为 k，源点连其他点的流量为 1。照最小链覆盖的建图方法建出二分图跑最小费用最大流即可。

有一个问题就是真能确保覆盖所有点吗？实际上可以，因为最小费用最大流保证流满，所以一定是走过所有点的。

后记

终于写完了，希望大家来看，网络流很好玩儿的。

题单排序顺序大致按照我的主观难度排序。

update 2024/4/13 修正笔误