网络流相关题目

· · 个人记录

链接：最小割&网络流应用

一些（许多）例题

这里收录一些思维难度较高，不易看出网络流的题。

P3973 [TJOI2015]线性代数

题意 : 给定一个 n * n 的矩阵 B 和一个 1 * n 的矩阵 C。求出一个 1 * n 的 01 矩阵 A，使得 D=(A×B-C) × A^{T} 最大，其中 A^{T} 为 A 的转置，输出 D。

如果觉得这是个线性代数题，那就只能得到 30pts。

注意到要求的是 01 矩阵，且有好多 1 * xxx 和 xxx * 1等类型的矩阵。因此我们试着摆脱矩阵的限制，直接用表达式来表示 D。（可以用 n = 3 的情况来模拟一下）

D = \sum_{i,j<=n}{b_{i, j} * a_i * a_j} - \sum_{i=1}^{n}{c_i * a_i}

然后我们发现实际上就是关于 a_i，对于参数 b 和 c 的选择问题。

首先我们先假设先选择了所有的 a_i，那么我们就要付出 \sum{c_i} 的代价。但是我们有时候可以进行反悔操作。即，我们可以选择放弃 a_i, a_j，来以 b_{i, j} 的代价来代替 c_i, c_j 的代价。

具体些，我们先把所有收益 \sum{b_{i,j}} 拿上，然后考虑付出最少的代价。我们可以选择付出 c_i + c_j 的代价，也可以选择 b_{i, j} 的代价。

更具体地，我们用一堆节点来表示 b_{i, j}，用一些节点来表示 c_i。当我们选择了 b_{i, j} 时，就不能再选择 c_i, c_j了；当我们选择 c_i 时，我们也不能选择 b_{i, j}。

再具体些，我们将 b_{i, j} 与源点相连，将 b_{i, j} 与 c_i, c_j 相连，将 c_i 与汇点相连。 然后跑最小割（最大流）。割掉哪个就表示选哪个作为代价。 最后答案为 \sum{b_{i, j}} - maxflow

将两个矛盾点强制选择其一，再考虑反悔来回避矛盾，是最小割问题的一种常见思想，类似的思想还应用于 最大权闭合子图 的最小割理解。类题可见 : P4307 [JSOI2009]球队收益 / 球队预算 （其中还涉及到拆边思想）

P2046 [NOI2010]海拔

给一张双向网格图，点有点权，每条边有两个权值（双向）。对于每个边权，它对答案造成的贡献为 val[e] * max(height[v] - height[u], 0)（其中这条边为 u -> v）。已知height[1, 1]=0，height[n, n]=1。其余点权可以自由控制，为实数。求全局最小代价。

如果左上角和右下角权值都为 0，那么显然全局最优解就是0（所有点权都为0）。

现在右下角为 0.我们考虑每一条左上到右下的路径，有下降显然是不优的（因为要对 0 取 max，所以两点权值相等和权值下降时一样的）。那么如果我们上升，每次上升 0.多，怎么样？反正总和为 1，我们不如直接找到最小边权，让它乘上个 1 不是更好？

对于整个网格来说，我们让它左上全为 0， 右下全为 1，中间挑选几个升到 1 的小边权的边即可。即，挑选一些边，使得左上部分的点属于 S，右下部分的点属于 T。并且要求边权和最小。

因此，答案就是网格的最小割。可以用对偶图来优化。

### [P3980 [NOI2008]志愿者招募](https://www.luogu.com.cn/problem/P3980) $n$ 天， $m$ 类志愿者，每类志愿者可以从 $S_i$ 工作到 $T_i$，一共花费 $c_i$。现要求第 $i$ 天的志愿者数量不少于 $a_i$，求所需最小费用。 我也不知到大佬们是怎么想出来的（直接模拟题意？），见图方式大概是这样： 1. 一共 $n + 1$ 个点，其中 $i$ 向 $i + 1$ 连边，表示第 $i$ 天，流量限制为 $[a_i, +∞]$，费用为0. 2. 对于每一类志愿者$(a_i, b_i, c_i)$，我们从 $b_i + 1$ 点向 $a_i$ 点连一条流量限制为 $[0, +∞]$，费用为 $c_i$的边。大概就是说从 $a_i$ 到 $b_i$ 这些天（即图中的那些边）添加一种可循环流，其花费为 $c_i$，可供流动以达到“天”边的流量下届。 3. 没有超级源点汇点，直接跑无源汇有上下界最小费用最大流。 这说明：**我们有时候可以用边的流量下届来限制一些必须完成的条件，用环流来提供达到限制的可能**，这样就不用建立超级源汇了。 ### [P4553 80人环游世界](https://www.luogu.com.cn/problem/P4553) 题意 : n个国家从左到右排列， m 个人从左到右游历这 $n$ 个国家。对于游历了 $P_1, P_2, ..., P_k$ 国家$(0 <= k <= n)$的人，需要的飞机费用为 $fare_{P_1, P_2} + fare_{P_2, P_3} + ... + fare_{P_{k-1}, P_k}$（$fare{i, j}$ 已知）。现已知到达每个国家的人数 $V_i$，求最小总花费。 每个国家可以被当作开始的国家游历，也可以由一些人做飞机来游历。游历一个人就要答案加一。同时，一个国家被某个人游历完，这个人还可以坐飞机去其它国家。 到达每个国家的人数限制比较严格，必须是给定的某个数。但是以某个国家为初始国家的人数不确定，但是总人数是给出上界的（每个人可以一个国家也不游历）。 - （边以 $(low, up, fare)$ 的格式表示） - 将国家拆成两个点；建立一个副源点 $S'$；建立一个源点 $S$，并 $S'$ 向 $S$ 连边$(0, m, 0)$，流量（总人数）限制在 0 到 $m$ 之间，不花钱。 - 由源点 $S$ 连向所有国家的第一个点边$(0, inf, 0)$，表示初始国家，不限制人数（确切地说，不在这里限制），不花钱； - 所有国家的第二个点向汇点连边$(0, inf, 0)$，仅方便统计答案，不限流量，不花钱。 - 所有国家第一个点向第二个点连边 $(V_i, V_i, 0)$，表示进行游历，流量（人数）严格为 $V_i$，不花钱。 - 每个国家的第二个点向其右边国家的第一个点连边 $(0, inf, fare_{i, j})$，表示游历完后可以坐飞机到达另一个国家（当然也可以不去，直接流向汇点),不限人数，但要交费。 最后跑有源汇有上下界最小费用可行流。 ### [P2469 [SDOI2010]星际竞速](https://www.luogu.com.cn/problem/P2469) #### 题意： n个点，m条边的有向无环图。边有边权。点有点权。现要求找到若干条路径，**将每个点遍历一次且仅一次**，最小化： $$\sum_{chain}(val[start~point] + \sum_e{val[e])}$$ #### Solution 因为每个点都只被遍历了一次且仅一次，并且遍历到每个点都需要付出一定的代价。 具体来说，我们将答案拆分，拆成 $start~point$ 对答案的贡献 和 路径上其它点对答案的贡献。 如果该点作为起点，那么需要花费该点点权的代价（①）； 如果该点作为链上其它点，那么需要花费上一个点连向这个点的边权这么多代价（②）。 还有一些限制：每个点入度出度必须为1（③），包括起点（从虚拟节点走过来）和终点（走向虚拟节点）。因为每个点都只能被遍历到一次，因此所有边的容量应该都为1。没了。 于是有如下建图方式： - 将点 $x$ 拆成出点 $x$ 和入点 $x'$。 - $S$ 向所有的 $x$ 连边，所有的 $x'$ 向 $T$ 连边，容量均为1，不花钱。（③） - 从 $S$ 向所有的 $x'$ 连边，容量为1，费用为点权。（①） - 从 $x$ 向所有能到达的 $y'$ 连边，容量为1，费用为边权。（②） ### [P3227 [HNOI2013]切糕](https://www.luogu.com.cn/problem/P3227) #### 题意: 给一个点带权（非负）的长方体点阵，要求在每一数列中选择一个点，符合相邻数列所选择的点的高度差不超过 $d$，要求最大化选出的点的和。输出最大点权和。 $n, m, h <= 40

题解：

题解

如果 d >= h，那么我们就可以肆无忌惮地选点，自然是选择每一列中的最小点。如果把每一列都串成串，那么就是选择每一列中的最小割点。

我们多建一层，然后把点权放在相邻层间的边上。

现在有了 d 的限制，也就是说，如果选择了某一列的第 i 层的点，那么相邻列的 1, 2, 3, ..., i - d - 1 层的点和第 i + d + 1, ... h 层的点都不能选了，那么我们就可以根据此限制，让选择不合法点对不能构成最小割（类似二元关系模型的某些思想）。可行的方法为：将某一列的第 i 层点连向相邻列的第 i-d 层点，这样如果我们选择了不合法点对，就不能构成最小割（没有完全割断）。

P4382 [八省联考2018]劈配

题意：

我们要求排名靠前的选手尽可能地实现其最高的志愿。 每位选手还有一个期望志愿，实现不低于该志愿都能够满足该选手的期望。 要求合法安排方案，输出最优情况下这 $n$ 名选手的第几志愿被实现；同时输出每名选手至少需要提升几名才能达到其期望。（无解特判） $n,m<=200,c<=10

题解

用自己的思路做出来的第一道n省联考题

不得不说，这道题真的不是很难，况且暴力+特判+贪心就有60分。

题目明显提示二分图（网络流）。

题意明显证明网络流（最优情况 -> 最大流。每位选手只能选一个导师；每个导师团队最多容纳 b_i 个人 -> 限制流量。根据后面选手的选择情况，可能会对前面选手的选择进行微调 -> “退流”操作。200范围 -> 贪心不好搞 -> 网络流）

很自然想到选手与导师匹配。第一问就从前往后模拟题意:每次尝试选该选手的更高志愿（向导师连边），若可以增广，则保留边，记录答案；否则删边尝试下一个。每次增广大致 O(n)，最多增广 O(n) 次。最终复杂度大致 O(n^2)

第二问暴力枚举 O(n^4)，二分模拟 O(n^3logn)，但是估计跑不够。

实际上求第一问的时候顺便求一下每一位导师团队最早什么时候满员且无法通过调整使其多出来一点流量（最小割必须边）。每位选手的期望导师的“满流时间”最大值即可更新答案。复杂度 O(n^2)。

题目大概可以出到500，因为极限情况复杂度是 O(n^3) 的（n^2 遍 bfs)

由于这道题要支持删除最后加入的某些边，因此用vector 存图会更方便些。

弧优化：记录当前 vector 的下标。

反边：每一条边单独开一个存反边下标的数组。（反边的起点一定是正边的终点）

P4003 无限之环

如何看出网络流？

水管 -> 点；

水管的连接 -> 匹配；

不漏水 -> 跑满流；

最小旋转次数 -> 最小费用

如何支持旋转？

分类讨论。

首先拆点（上下左右中），模拟题意连初始的免费边，再讨论旋转后边的情况以及费用情况。

能否不拆点？

否

拆点后便于我们控制原来的某一方向的改变，从而做到有条不紊；如果不拆点，就没有方向的限制了，可能会把一个 L 型搞成 | 型，然后WA掉。

如何处理连接？

二分图匹配.

像这种网格题（甚至三位方块题），应该能迅速地想到拆出“行点”“列点”的模型（互斥） 或者 黑白染色后匹配的模型（匹配）。

注意右部图的连边全部是反过来的。

#6058. 百步穿杨

如何解决线路交叉问题?

首先根据套路，我们将每一条“路径”都自动给它一个收益10，然后再让每条“路径”放弃一些收益来保证合法，题目转化为最小割问题。

现在，我们要做的是，如果两条路径相交，那么我们需要视其为不合法情况，并且将其中一条路径在“相交点”之前拦下。如果我们能够构建一张图，能够沿着第一条路径从 S 以及路径起点走到 “相交点”，再沿着第二条路径向回走走到路径起点以及 T，路径上的边的权值设为 在这里拦下的额外花费（放弃的收益），那么问题得解。

一种可行的建图方式：

其中灰色边表示无法被割掉的边。每个割点被拆成两个点（黑点和蓝点），由横点向竖点连灰边。边权：10 - 靠近路径起点的那个点点权。割掉一条边相当于把路径拦在了靠近路径起点的那个点，割掉10相当于不选。这样，每一种最小割都对应一种合法的调整方式。

注意拆出来的两个点之间只能连单向边，否则会使得两个都没过交叉点的情况变为不合法情况

代码：（先借用别人的代码）loj record 终于有我的了：my record

CF802C Heidi and Library (hard)

看到数据范围应该能猜到要用网络流，但是尽管这样这题还是非常难想。

考虑先把所有书都买上，然后如果到用的时候有就“卖掉”这本书。

但是如果这样，如果下一天要用的书存在，这一天能留 k 本书；如果下一天要用的书不存在，这一天能留 k-1 本书，比较难控制。

于是我们在用留着的书的前一天就先“卖掉”这本书，这样就能腾出空间再“买”这本书了。

建图：

每天拆点 x,x'，s \to x(1,v),x \to x'(1,0),x' \to t(1,0),x_i \to x_{i+1}(k-1,0),x_{i} \to x_{pre}' (1,-v)

跑最小费用最大流。由于每一天的流出的流量一定为 1，能保证每天的书只能被之后“卖”掉或被现在扔掉。

2021.6.2 Update：

还有一种比较简单粗暴的拆点做法：类似 收藏家 那题的做法，我们把书按时间拆点，流量表示书架的位置。某时间书有流量表示书架上。可以扔一本书，从这一时间指向下一时间的另一本书，费用为那本书的价格。强制经过某些时刻的某一本书的流量为一，跑有源汇有上下界最小费用可行流。

这种做法点边会多不少，但是似乎也可以用类似收藏家那题的方法优化一些。

习题

这里存放较为简单的网络流题。

P2153 [SDOI2009]晨跑

我首先想到的是类似于贪心 + 反悔的思路：

随便找到一条最短路，然后再找另一条最短路，如果有重合，就给其中一条改变的机会。

然后发现自己在模拟最小费用最大流。于是直接写个最小费用最大流就过了。

注意：要拆点。因为限制是在点上。

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

...

P2472 [SCOI2007]蜥蜴

这里涉及到“某个点最多只能被经过 h 次”的问题，可以把点拆成入点和出点，在之间的边上进行限制。

P2598 [ZJOI2009]狼和羊的故事

最小割典型例题的双倍经验。

P3965 [TJOI2013]循环格

不是很简单，但是和那些网络流的毒瘤题相比要好受一些。

显然题目意思是最后要把所有的点的入度和出度全部边为1.（当然出度怎么着都是1）

使用二分图来解决。左部图管出度，向右部图的点连原图中的边；左右部图与S(T)的连边的流量都限制为1。然后我们给每个点改变方向的机会，但是要付出一定的代价。然后最小费用最大流。

P3159 [CQOI2012]交换棋子

题意可以转化为一股流从某些点出发流向另一些点，并且其他算法看起来很不可做的样子，因此可以网络流。

又由于有一些限制，在限制范围内最小化次数，因此考虑费用流。

又因为限制在点上，因此考虑拆点；又因为进入一个点和出一个点都要花费次数限制，因此考虑拆三个点，把限制放在两条边上；又因为状态已经告诉我们某个点的流入流量和流出流量的关系（相等或者差一），因此可以均分流量+微调。

UVA1751 Mission Improbable

网络流在这道题里面更像是一个工具，就是当有多种贪心策略且部分互斥时，使用网络流无脑计算最优解。

注意开long long，注意将inf改得更大一些。

P3191 [HNOI2007]紧急疏散EVACUATE

分层图网络流。按时间分层。

由于不同时间情况不同，因此需要按时间分层；二分答案后转为判定问题。

对所有点都分层复杂度爆炸，因此只对部分关键点（门）分层。

HACK

题意：给一DAG，边有正边权。找一组边，使得S到T的所有路径都仅经过一条你找的边集中的边。最小化边集权值和。

发现如果不是“仅经过一条”，而是“经过”的话，就是最小割。否则，“二元关系图解”中中间的那一对边只保留一条边，就是一个反例。那么我们只需要把每条边的反向边流量设为inf，即补充上那对边的另一条边（不让从T集返回S集，如果返回，让其不为最小割），即可。

P3705 SDOI2017新生舞会

鸽了

P2570 [ZJOI2010]贪吃的老鼠

很难，很ZJOI

Continued...