警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「题目汇总」网络流 24 题

本蒟蒻在此祝 dalao 们新年新进步,新年新 AK!

此处为网络流 24 题的题解汇总。

传送门:LOJ洛谷

注:机器人路径规划问题咕咕了搭配飞行员软件补丁负载平衡 太水不写。

Todo

机器人路径规划 Solution

餐巾计划

题意

传送门:洛谷 P1251 - 餐巾计划问题LOJ 6008 - 餐巾计划

\(n\) 天。第 \(i\) 天要 \(r_i\) 块餐巾。买一块餐巾 \(P\) 分,快洗部洗一块要 \(M\) 天,\(F\) 分钱;慢洗部洗一块要 \(N\) 天,\(S\) 分钱。允许延期送洗。问最少花多少钱。

解法

把餐巾视为流量,代价视为费用。对于每一天,拆成早上和晚上,即 \(x\)\(x’\)

每天晚上将获得 \(r_i\) 块脏餐巾。所以连接 \(S \xrightarrow{r_i, 0} x'\)

每天早上要使用 \(r_i\) 块干净餐巾。所以连接 \(x \xrightarrow{r_i, 0} T\)

每天草上可以买任意多块餐巾。所以连接 \(S \xrightarrow{+\infty, P} x\)

快洗部用 \(M\) 天将任意多块餐巾洗干净。所以连接 \(i \xrightarrow{+\infty, F} (i + M)\)

快洗部用 \(N\) 天将任意多块餐巾洗干净。所以连接 \(i \xrightarrow{+\infty, S} (i + N)\)

其中 \(x \xrightarrow{a, b} y\) 代表从 \(x\)\(y\) 连接一条流量为 \(a\),费用为 \(b\) 的有向边。

代码

LOJ洛谷 的输入格式不一样。好坑~

星际转移

题意

传送门:洛谷 P2754 - 家园LOJ 6015 - 星际转移

有 $n+2~([-1, n]) $ 站和 \(m\) 趟班车,每趟班车会在一个站点集合 \(v_{i,0} \sim v_{i, c_i-1}\) 里轮流转。第 \(i\) 趟班车可以坐 \(h_i\) 人,最开始 \(0\) 号站有 \(k\) 个人,问最快要多久所有人都转移到 \(-1\) 站。

题解

考虑按时间拆点。令 \(t\) 时刻的 \(i\) 号站为 \((t, i)\)

\(0\) 时刻,\(0\) 站有 \(k\) 个人,所以 \(S \xrightarrow k (0, 0)\)

以后的每一时刻,每个站的人可以选择待在这个站,也可以选择坐车。即 \((t, i) \xrightarrow1 (t+1, i)\)\((t, v_{i, t \bmod c_i}) \xrightarrow1 (t+1, v_{i, (t+1) \bmod c_i})\)

然后求 \((0, 0)\)\((t, -1)\) 的最大流。如果达到了 \(k\) 就输出,否则继续。

注意加边求最大流不需要清空流量。

代码

太空飞行计划

题意

传送门:洛谷 P2762 - 太空飞行计划问题LOJ 6001 - 太空飞行计划

\(n\) 个实验,\(m\) 种器材。实验 \(i\) 需要使用 \(R_i\) 这个集合中的仪器,价值是 \(p_i\)。仪器 \(i\) 的代价是 \(c_i\),可以多次使用。问如何实验可以获利最大。

解法

最大权闭合子图模板题。

\(S \xrightarrow{p_i} \text{实验}_i\)\(\forall j \in R_i, \text{实验}_i \xrightarrow{+\infty} \text{仪器}_j\)\(\text{仪器}_i \xrightarrow{c_i} T\) 即可。

答案是 所有正权边的和减去最小割

答案为 Dinic 中最后一次求 bfs 时仍有 level 的点。(其它点被割掉了)

代码

LOJ 不允许行末空格……

试题库

题意

传送门:洛谷 P2763 - 试题库问题LOJ 6006 - 试题库

\(n\) 道题,\(k\) 种类型。每道题的类型是集合 \(T_i\)。你要从中选出 \(a_i\)\(i\) 类型的题,每道题只能选一次。求一种可行的选择方案。

解法

考虑用流量限制每道题的选择次数。并对每道题和每个类型构点。

首先从 \(S\)\(\text{题目}_i\) 连一条流量为 \(1\) 的边,即每道题只能选一次;

然后从 \(\text{类型}_i\)\(T\) 连一条流量为 \(a_i\) 的边,即每种类型需要选 \(a_i\) 道;

最后 \(\forall j \in T_i\),从 \(\text{题目}_i\)\(\text{类型}_j\) 连边,即每道题可以以相应类型的名义被选出。

方案即是所有 题目到类型 的连边中满流的那些。如果流量不满则无解。

代码

这次毒瘤 LOJ 数据存在 \(\mathbf{a_i = 0}\) 的情况

最小路径覆盖

题意

传送门:洛谷 P2764 - 最小路径覆盖问题LOJ 6002 - 最小路径覆盖

给一张 DAG,求最少用几条不相交简单路径可以覆盖整张图的所有点。并求出方案。

解法

如果没有最小的限制,那么直接输出 \(n\) 就好了 2333(逃

1
2
3
WA Output:
1 2 ... n
n

注意到这 \(n\) 条路径是可以合并的。

如果一条路径的终点和另一条路径的起点有连边,那么这两条路径是可以合并的。

但是一个终点或起点只能使用一次。比如三条路径 \(1 \to 3, 2 \to 3, 3 \to 4\),你只能合并两条。

那么这道题就转化为了:最大化一个边集,使得边集中每个起点和终点都只使用过一次。即 最大独立边集

这个显然是可以最大流求的。把拆成入点 \(x\) 和出点 \(x’\)。从原点到 \(x'\) 连一条容量为 \(1\) 的边,从 \(x\) 到汇点连一条容量为 \(1\) 的边。边权用来限制每个起点或终点的使用次数。

对于每条边 \(x \to y\),连接 \(x' \xrightarrow1 y\)

因为每一条这样的边都意味着一次合并,所以答案是 \(n - \text{最大流}\)

代码

LOJ 终于不毒瘤了!热泪盈眶

魔术球

题意

传送门:洛谷 P2765 - 魔术球问题LOJ 6003 - 魔术球

\(n\) 根柱子。你要往柱子上放编号为 \(1, 2, 3, \cdots\) 的球。满足同一根柱子上相邻两个球的编号之和为完全平方数。

\(n \le 55\)

解法

考虑贪心。从 \(1\) 开始枚举球的编号。如果现成的柱子可以放这个球,那么直接放上去。否则就开个新柱子。

因为每一根柱子能否插入一个球,只和柱子顶端的球有关。所以放着能插入的柱子不管,而是另开一根柱子一定不会使答案变优。

这真的是网络流 24 题么?

代码

震惊!这货仍然全 OJ 通用!(逃

最长递增子序列

题意

传送门:洛谷 P2766 - 最长不下降子序列问题LOJ 6005 - 最长递增子序列

给一个序列 \(a_{1 \cdots n}\),求:

  • 最长不下降子序列长度
  • 最多可以取出多少个最长不下降子序列
  • 允许无限次使用 \(a_1, a_n\),最多可以取出多少个最长不下降子序列

注意:规则 3 中「无限次使用」必须满足 取出的每个序列下标不重复

解法

第一问显然可以暴力 DP。令 \(len\) 为最长不下降子序列的长度。

第二问考虑最大流。我们希望每条从 \(S\)\(T\) 的路径都代表一条 长度正好为 \(\mathbf{len}\) 的路径

\(dp_i\) 为以 \(i\) 为结尾的最长不下降子序列长度。

那么我们可以按照 DP 值的转移路线连边。即 \(\forall dp_j + 1 = dp_i, j \xrightarrow1 i\)

然后我们考虑从 \(S\) 连向 \(dp_i = 1\) 的所有点,从所有 \(dp_i = len\) 的点连向 \(T\)

但是每个元素只能用一次。按照套路,我们把每个点拆成入点和出点,在入点和出点之间连一条容量为 \(1\) 的边。

最后求个最大流就好了。

第三问我们只要解除 \(a_1\)\(a_n\) 的次数限制就好了。

即连接 \(S \xrightarrow{+\infty} 1 \xrightarrow{+\infty} 1'\)。如果 \(dp_n = len\),连接 \(n \xrightarrow{+\infty} n' \xrightarrow{+\infty} T\)

然后我在 LOJ 上就被叉掉了。

交 LOJ 记得特判 \(\mathbf{n = 1}\)

再求一次最大流就好了。

代码

航空路线问题

题意

传送门:洛谷 P2770 - 航空路线问题LOJ 6122 - 航空路线问题

求两条途径点数尽可能多的从 \(1\)\(n\) 的不相交路线(\(1, n\) 除外)

解法

看到不相交,考虑拆点。

按照套路,每个点拆成入点和出点 \(x, x'\)。然后从 \(x\)\(x'\) 连一条容量为 \(1\),费用为 \(0\) 的边。

输入中每一条 \(x \to y\) 的边在网络流中就直接将 \(x'\)\(y\) 连一条容量为 \(1\) 的边。

因为希望经过的点数尽量多,所以将费用设为 \(-1\) 跑最小费用最大流即可。

输出直接沿着满流边 dfs 两次就好了。注意输出顺序。

然后这题有一个坑点:必须特判 \(1 \leftrightarrow n\) 的边。

代码

又是一份两个 OJ 都能过的代码~

方格取数

题意

传送门:洛谷 P2774 - 方格取数问题LOJ 6007 - 方格取数

给你一个 \(n\times m\) 的棋盘,每个格子上有一个数。你要在取的格子包含公共边的前提下使数的总和最大。

解法

首先对棋盘黑白染色,建二分图,在相邻的格子之间连边。

注意到我们要求的其实是 二分图的最大权独立集

又有 (二分图)最大独立集 = 点权和 - 最大权匹配,所以我们只需要求出最大匹配就好了。

代码

机器人路径规划

论文题,咕咕咕。

圆桌聚餐

题意

传送门:洛谷 P3254 - 圆桌问题LOJ 6004 - 圆桌聚餐

\(n\) 张餐桌,\(m\) 个单位。第 \(i\) 个餐桌容量为 \(c_i\),第 \(i\) 个单位人数为 \(r_i\)。每个餐桌不允许出现两个同一单位的人。求一个可行的方案,或输出 \(0\)

解法

考虑对桌子和单位构点。从源点连容量为 \(r_i\) 的边到单位 \(i\),从餐桌 \(i\) 连容量为 \(c_i\) 的边到汇点。

注意到每个单位只能在每张桌子上放一个人。考虑从每个单位向每张桌子连一条容量为 \(1\) 的边。

如果最大流小于人数和则无解。

否则对于每个单位,枚举它的出边,输出满流边的终点即可。

代码

骑士共存问题

题意

传送门:洛谷 P3355 - 骑士共存问题LOJ 6226 - 骑士共存问题

求带障碍的 \(n \times n\) 的国际象棋棋盘可以放多少个马,使得两两之间互相不能攻击。

解法

首先每个马只能攻击与自己颜色不同的格子。考虑二分图。

还是老套路,将可以互相攻击的格子之间连一条边,然后求 二分图的最大独立集 即可。

因为 (二分图)最大独立集 = 点数 - 最大匹配,所以我们只需要求出最大匹配就好了。

代码

火星探险问题

题意

传送门:洛谷 P3356 - 火星探险问题LOJ 6225 - 火星探险问题

有障碍、多路径的方格取数(LP1004)。

解法

注意到一个点只能取一次。根据套路我们拆成点 \(x, x'\)

因为第一个踩到的机器人会采集,所以在 \(x\)\(x'\) 之间连一条容量为 \(1\),费用为 \(-1\) 的边。

因为接下来踩到的什么事都没有,所以在 \(x\)\(x'\) 之间连一条容量为 \(+\infty\),费用为 \(0\) 的边。

然后从 \(S\)\((1, 1)\),从 \((n, m)'\)\(T\) 连一条容量为 \(k\)、费用为 \(0\) 的边。

然后跑费用流就好了。输出方案用 DFS。

注意:在输出方案的时候,不要经过入点,否则会重复输出。

代码

最长 k 可重线段集问题

博客传送门:这里

最长 k 可重区间集问题

题意

传送门:洛谷 P3358 - 最长k可重区间集问题LOJ 6014 - 最长 k 可重区间集

给一个开区间集合 \(I\),问如何选一个集合 \(S \subseteq I\),使得 \(\forall i, \sum_{j \in S}[i \in j] \le k\),且 \(\sum_{i \in S}|i|\) 最大。求最大值。

解法

首先离散化区间端点,将值域缩小到 \([1, 2n]\)。然后 \(S \xrightarrow{k, 0} 1, i \xrightarrow{k, 0} (i+1), 2n \xrightarrow{k, 0} T\)

对于每条线段,我们从左端点向右端点连一条流量为 \(1\) 的边。这会使开区间 \((l, r)\) 的可支配流量 \(-1\),代表能选的互相覆盖的区间数减了 \(1\)

因为我们希望选的边长度和尽量大,这条边的费用为 \(\mathbf{l - r}\)

跑一个最小费用最大流后,费用的相反数即为答案。

代码

LOJ 数据竟然有 \(\mathbf{r > l}\) 的情况……反人类

汽车加油行驶问题

题意

传送门:洛谷 P4009 - 汽车加油行驶问题LOJ 6223 - 汽车加油行驶问题

给一个 \(n \times n\) 的地图。你要从 \((1, 1)\)\((n, n)\)

  • 你的油箱最开始是满的,每走一格耗一格油,总共有 \(k\) 格油。
  • 你可以往→和↓两个方向走。如果你逆行就要罚款 \(B\) 块。
  • 有一些点有加油站,踩到加油站就要被强制消费 \(A\) 块并加满油。
  • 如果你想在没加油站的地方加油,你可以付 \(A+C\) 块。这样你的车就会被膜法加满油。

问你最少要被坑多少钱。\(n \le 100, k \le 10\)

解法

我偏不用网络流

考虑分层图最短路。\((lv, x, y)\) 代表你在 \((x, y)\) 处,油箱里有 \(lv\) 格油。

那么对于加油站,有 \((lv, x, y) \xrightarrow A (k, x, y)\)

对于非加油站的点,有下面几种边:

  • 空中加油:\((lv, x, y) \xrightarrow{A+B} (k, x, y)\)
  • 顺行:\((lv, x, y) \xrightarrow0 (lv-1, x + 1, y), (lv-1, x, y + 1)\)
  • 逆行:\((lv, x, y) \xrightarrow B (lv-1, x + 1, y), (lv-1, x, y + 1)\)

然后跑一个 SPFA 就好了死不掉的

代码

孤岛营救问题

题意

传送门:洛谷 P4011 - 孤岛营救问题LOJ 6121 - 孤岛营救问题

给你一个 \(n \times n\) 的魔塔地图。每把钥匙可以用无数次。问要多久可以从 \((1, 1)\) 走到 \((n, n)\)魔塔玩家的福音

钥匙最多有 \(10\) 种。

解法

考虑分层图。\((lv, x, y)\) 代表你在 \((x, y)\) 处,手上的钥匙集合是 \(lv\)(状压)。

\(wall_{x, y, dir}\)\((x, y)\)\(dir\) 方向上的墙需要的钥匙种类,令 \(key_{x, y}\)\((x, y)\) 上的钥匙集合。

为了方便,不可通过的墙可以将 \(wall_{x, y, dir}\) 设为 \(2^{11}\)

因为所有类型门都已经归为钥匙门的子集,我们可以直接按下列方式连边:

\(\forall (lv, x, y, dir), \text{if}~wall_{x,y,dir} \subseteq lv, \text{then}~(lv, x, y) \xrightarrow1 (lv \operatorname{or} key_{nx, ny}, nx, ny)\)。其中 \(nx, ny\) 代表新的坐标。

因为所有边的边权都是 \(1\),所以直接 BFS 即可。

代码

深海机器人问题

题意

传送门:洛谷 P4012 - 深海机器人问题LOJ 6224 - 深海机器人问题

有一个 \((n+1) \times (m+1)\) 的棋盘,每条边上有一个数字。有 \(a\) 个起点和 \(b\) 个终点,每个起点有 \(k_i\) 个机器人,每个终点可以存 \(r_i\) 个机器人。机器人走一条边就会收集这条边的数字。问能收集到的数字的和的最大值是多少……

本蒟蒻脑子抽了,请自行查看原题

解法

根据 火星探险问题 的套路,我们在两两格子之间连两条边:一条边容量为 \(1\),费用为权值的相反数,另一条容量无限,费用为 \(0\)

然后对于每个起点,从源点连一条容量为 \(k_i\) 的边。终点同理。

代码

数字梯形问题

题意

传送门:洛谷 P4013 - 数字梯形问题LOJ 6010 - 数字梯形

给你一个 \(n\) 层的数字梯形,最顶层有 \(m\) 个数。你要求出 \(m\) 条从顶层各数出发的路径,满足下列三种规则:

  1. 路径的点和边都不能相交
  2. 路径的边不能相交
  3. 随你相交

使得这些路径上数字的总和最大。

解法

网络流大模拟……其实没什么思维难度吧……

第一问

注意到如果点之间不相交,那么边之间一定不相交。

点之间不相交直接套路拆点即可。在 \(x\)\(x'\) 之间连一条容量为 \(1\),费用为权值的相反数的边。

两个点之间连一条容量为 \(1\)、费用为 \(0\) 的边。

跑费用流即可。

第二问

懒癌发作,不想重新构图。

注意到第二问其实是删除了点的限制。所以直接在 \(x\)\(x'\) 之间连一条容量为 \(+\infty\) 的边。

……等等,还要在底层和 \(T\) 之间连一条容量为 \(+\infty\) 的边。不然路径终点仍然被限制了。

然后清空流量跑一遍费用流。

第三问

还是不想重新构图。

只需要把所有数字之间的边都扩容就好了。

然后再清空流量跑一遍费用流。

代码

分配问题

题意

传送门:洛谷 P4014 - 分配问题LOJ 6012 - 分配问题

\(n\) 件工作要分配给 \(n\) 个人做。第 \(i\) 个人做第 \(j\) 件工作产生的效益为 \(c_{i,j}\)。试设计一个将 \(n\) 件工作分配给 \(n\) 个人做的分配方案,使产生的总效益最大。

解法

显然对人和工作构点。人和工作是一一对应的,所以源点向每个人、每个工作向汇点连一条容量 \(1\) 费用 \(0\) 的边。

然后第 \(i\) 个人向第 \(j\) 个工作连一条容量 \(1\) 费用 \(-c_{i,j}\) 的边。最后求一个最小费用最大流即可。

代码

运输问题

题意

\(n\) 个仓库 \(m\) 个商店。\(i\) 仓库有 \(a_i\) 单位货物,\(i\) 商店需要 \(b_i\) 单位货物。\(i\) 仓库到 \(j\) 商店的运费是 \(c_{i,j} / \text{单位}\)。问最小运输费用和最大运输费用。

解法

对于第一问,只需要 \(S \xrightarrow{a_i, 0} \text{仓库}_i, \text{仓库}_i \xrightarrow{+\infty, c_{i,j}} \text{商店}_j, \text{商店}_i \xrightarrow{b_i, 0} T\) 然后跑最小费用最大流就好了。

第二问只要把仓库到商店的边费用取相反数再跑一遍就好了。

代码