希望能对做这套题的人有所帮助，去掉部分真的没什么意义的题。

前置知识：网络流

更好的阅读体验&目录链接

LOJ 真好，代码公开省了我很多空间QWQ

网络流24题虽然有好题，但是也有莫名其妙的……并没有想象中那么值得一做。

提交网站挂在LOJ，倒是很建议做完之后参考一下最优解为什么跑那么快。

以下是对于题目的类型归类，加删除线的是我感觉真的不用再做的题。不过评价可能有部分基于题目顺序。

二分图匹配 ：搭配飞行员，圆桌聚餐 ，最小路径覆盖

美妙拆点 ：最长递增子序列，餐巾计划，数字梯形 ，星际转移，航空路线

美妙拆边 ：深海机器人，火星探险（和深海机器人类似，但是如果要练习输出方案可以做这个）

最小割 ：太空飞行计划，方格取数，骑士共存（与方格取数类似）

费用流 ：分配问题 ，运输问题，最长 k 可重区间集（比后面那题少了个特判） ，最长 k 可重线段集

感觉过于基础的题 ：试题库

莫名其妙不用网络流的题 ：魔术球（网络流可做，但是第一反应贪心），软件补丁（状压最短路），负载平衡（均分纸牌），孤岛营救（状压最短路），汽车加油行驶

搭配飞行员

一架飞机需要一正一副两个飞行员，给出若干对正副飞行员（表示可以同机飞行），求最多可以配多少对。

Solution

很显然的二分图匹配。让我想跑匈牙利 不你不行。

考虑一个很基础的建模：

• 建立超级源点 $S$ ，向所有正飞行员连容量为 $1$ 的有向边；
• 建立超级汇点 $T$ ，向所有负飞行员连容量为 $1$ 的有向边；
• 如果两个飞行员能搭配，那么从正飞行员向副连一条容量为 $1$ 的有向边。

然后跑最大流即可。

代码链接

太空飞行计划

有 $m$ 个实验，第 $j$ 个实验用到了器材集合 $R_j$ ，配置仪器 $I_k$ 的费用为 $c_k$ ，实验 $E_j$ 有收益 $p_j$ ，求最大的净收入。

Solution

证明 建图方式：

• 起点向实验连流量为费用的边
• 实验向仪器连流量为 INF 的边
• 仪器向终点连流量为费用的边

答案就是总费用减去最小割。对于输出方案，发现 Dinic 跑 BFS 的时候，有层次标记的点就是残量网络上还剩下的点，而一个点流完了就说明仪器的费用不比收获小，那还不如不取，所以从源点 $s$ 开始的 BFS 之后，有标记的点就相当于选择的点。那么只需要正常执行完之后根据 $dis$ 输出即可。

代码链接 这道题的 IO 简直是杀人……

最小路径覆盖

给定有向图 $G$ ，设 $P$ 是 $G$ 的一个简单路集合，如果 $V$ 中每个点恰好在 $P$ 的一条路上，称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以长度可以为 $0$ . $G$ 的最小路径覆盖是所含路径条数最少的路径覆盖。求最小路径覆盖。

Solution

奇妙的模型，拆点转化成二分图匹配。我们将每个点 $i$ 拆成一个左部点 $x_i$ 和一个右部点 $y_i$ ，对于每一条边 $(i,j)$ ，连边 $(x_i,y_j)$ . 注意到二分图的任何一个匹配都对应了原图中的一个路径构造方案，如果没有匹配那么就是路径数=点数。而每增加一个匹配，就减少了一条路径，求最小路径覆盖就是要求最大匹配，跑最大流即可。

对于求方案，只需要在求出匹配之后沿着匹配边跳即可。

代码链接

魔术球

有 $n$ 根柱子，依次放入编号为 $1,2,3,\cdots $ 的球。每次只能在顶端放，且同一根中任何两个相邻球的编号之和为完全平方数。

求最多能放多少个球。

Solution

Link

圆桌聚餐

有 $m$ 个单位的代表参加会议，第 $i$ 个单位有 $r_i$ 个人。一共有 $n$ 张餐桌，每张可以有 $c_i$ 个人，且同一个单位的人不能在同一个餐桌。求一个合法的方案。

Solution

建立超级源汇，以单位为左部点，餐桌为右部点，$S$ 向所有左部点连容量为 $r_i$ 的边，每个左部点向所有右部点连容量为 $1$ 的边，每个右部点向 $T$ 连容量为 $c_i$ 的边。跑最大流（或者说最大匹配），如果最大匹配不等于人数那么无解，否则输出方案即可。

代码链接

最长递增子序列

给定正整数序列 $x_1\sim x_n$ ，计算其最长递增子序列的长度 $s$ ，求方案数，并计算如果能多次使用 $x_1,x_n$ 的方案数。

Solution

第一问：直接 $\mathcal{O}(n^2)$ DP。

第二问：把每个点拆成 $i,i+n$ ，然后将之间连一条 $1$ 的边，如果 $i$ 后面能接 $j$ （就是 $a[i]\leq a[j],f[i]+1=f[j]$ ），就连接 $i+n,j$ ，$S$ 与 $f[i]=1$ 的点相连，$f[i]=ans$ 的点与 $T$ 相连， 跑最大流。

第三问：依然拆点，如果 $i\neq 1,n$ 那么连接 $(i,i+n,1)$ ，否则是 $(i,i+n,n)$ （因为可以多次使用）；如果 $f[i]=1$ 且 $i\neq 1$ ，连接 $(S,i,1)$ ，如果 $i=1$ 那么 $(S,i,n)$ ；如果 $f[i]=ans$ ，且 $i\neq n$ ，那么 $(i+n,T,1)$ ，如果 $i=n$ 那么 $(i+n,T,n)$ .

代码链接

试题库

有 $n$ 道题，$k$ 个标签，每道有若干个标签，要求取出 $m$ 道题使得组成的试卷包含指定类型的试题。无解 No Solution! .

Solution

$S$ 向标签连“该类型选择题数”的边，标签向每个属于它的试题连容量为 $1$ 的边，然后试题再连向 $T$ 即可。

一开始脑子抽了居然以为 $\sum k[i]\neq m$ ……

代码链接

方格取数

$m\times n$ 的方格，每个方格有一个正整数。从中取数，使得任意两个没有公共边，且取出的数总和最大。

Solution

感觉我对最小割异常迟钝……

先对这个玩意儿黑白染色（其实就是作为左部点和右部点），然后每个黑色格子向四联通的格子连 INF 的边（不能同时选），$S$ 向左部连点权，右部向 $T$ 连点权，答案就是总和减去最小割，跑最大流即可。

代码链接

餐巾计划

一个餐厅在连续的 $n$ 天里，第 $i$ 天需要 $r_i$ 块餐巾，新的餐巾价格为 $P$ ，洗一块旧的餐巾需要 $M$ 天，价格为 $F$ ，或者用 $N$ 天，价格为 $S$ ，求满足需求的最小花费。

Solution

美妙费用流。考虑拆点，把一天拆成新的毛巾（买的）和旧的毛巾（洗好的）。

• 从 $S$ 向所有干净点连费用为 $P$ ，流量 INF 的边（购买）；
• 从干净点向 $T$ 连费用为 $0$ ，流量为 $r[i]$ 的边（提供）；
• 从 $S$ 向脏点连费用为 $0$ ，流量为 $r[i]$ 的边（丢出来的处理物）；
• 从脏点向 $m$ 天后的干净点连费用为 $F$ ，流量为 INF 的边（快洗）；
• 从脏点向 $n$ 天后的干净点连费用为 $s$ ，流量为 INF 的边（慢洗）；
• 从脏点往下一个脏点连费用为 $0$ ，流量为 INF 的边。

跑费用流即可。

代码链接

软件补丁

有 $n$ 个错误和 $m$ 个补丁，对于每个补丁，当且仅当错误包含 $B_1(i)$ 中的所有错误，不包含 $B_2(i)$ 的任何错误时可以使用，效果是修复错误集合 $F_1(i)$ ，加入错误集合 $F_2(i)$ ，每个补丁有耗时。求没有错误的最小耗时。

Solution

$\huge \color{yellowgreen}{去你的网络流24题}$

这明明是状压最短路……

$n\leq 20,m\leq 100$ ，所以可以直接把 $20$ 位压成一个状态，表示当前有哪些错误。从 $2^n-1$ 开始，跑最短路，每次枚举有哪些补丁可以用即可。

代码链接

数字梯形

给定一个 $n$ 行数字组成的数字梯形，第一行有 $m$ 个数字。分别求出满足以下规则的最大总和：

1. 从顶至底 $m$ 条路径互不相交
2. 从顶至底 $m$ 条路径仅在节点处相交
3. 从顶至底 $m$ 条路径仅在节点处或边相交

Solution

第一问：每个点拆成两个点 $X,Y$ ，容量为 $1$ ，费用为这个数，每个点的 $Y$ 向能到达的 $X$ 点连边。$S$ 向第一层的 $X$ 连边，最后一层的 $Y$ 向 $T$ 连边，容量为 $1$ ，费用为 $0$ ，跑最大费用最大流。

第二问：不拆点，直接连边，但是最后一层的点直接连 $T$ ，容量为 INF ，费用为这个数。

第三问：直接选，没有限制，相当于所有边的容量都是 INF。

好好的问题偏要 $3$ 个一起来增加码量 (ノ｀Д)ノ

代码链接

运输问题

有 $m$ 个仓库和 $n$ 个零售店，第 $i$ 个仓库有 $a_i$ 的货物，第 $j$ 个零售店需要 $b_j$ 的货物，供需平衡。从第 $i$ 个仓库运送一单位货物到第 $j$ 个零售店需要 $c_{i,j}$ 的费用，求满足供需的最少费用。

Solution

最小费用最大流。

• $S$ 向 $m$ 个仓库连流量为 $a_i$ ，费用为 $0$ 的边
• $m$ 个仓库向 $n$ 个零售店连流量为 INF ，费用为 $c_{i,j}$ 的边
• $n$ 个零售店向 $T$ 连流量为 $b_j$ ，费用为 $0$ 的边。

代码链接

分配问题

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

Solution

上一题的简化版。把所有流量改成 $1$ 即可。

代码链接

负载平衡

有 $n$ 个环形排列的仓库，每个都有一定的货物。求最少的搬运量使得库存相同（只能在相连间搬运）。

Solution

均分纸牌裸题。

代码链接

最长 k 可重区间集

给定 $n$ 个开区间的集合 $I$ 和一个正整数 $k$ ，从中选取开区间集合 $S\subseteq I$ ，所得实直线 $L$ 的任何一点 $x$ ，$S$ 中包含 $x$ 的开区间个数不超过 $k$ ，且 $\sum_{z\in S}|z|$ 最大。求最大值。

Solution

显然并不是所有点都有用，只需要保留所有端点即可。所以首先要离散化，这样点的个数至多为 $2n$ .

每个点向下一个点连边，容量为 $k$ ，费用为 $0$ 。对于每个区间 $l,r$ ，从 $l$ 向 $r$ 连容量为 $1$ ，费用为区间长度的边。最后，$S$ 向第一个点连容量为 $k$ ，费用为 $0$ 的边限流，最后一个点向 $T$ 同理，直接跑最大费用最大流即可。

代码链接

星际转移

有 $n$ 个点和 $m$ 条船，每条船有容量 $H_i$ ，一次行驶费用为 $1$ ，且周期性停靠一系列点。求从 $S$ 到 $T$ 最大流至少为 $k$ 的最小费用。

Solution

哦这该死的周期没法下手。所以只能一天一天来。这样就需要枚举答案。

其实枚举答案不需要二分。如果逐个枚举能够在原先的残量网络上加边，二分要重新建图，效率反而不如直接枚举。

但是这样对于“周期”还是没法连边，所以考虑拆点，把一个点按“点+秒数”拆开，然后随着枚举的答案新建对于新的一秒的一套点。

源点 $S$ 向所有时间点的起点连容量为 INF，费用为 $0$ 的边；同理，所有时间的终点向 $T$ 连容量为 INF ，费用为 $0$ 的边。

每个点向下一秒的自己连容量为 INF ，费用为 $0$ 的边。

对于每一艘船，（如果停靠在了当前点）向下一秒的下一个点连容量为 $H_i$ ，费用为 $1$ 的边。

然后每次跑最小费用最大流即可。注意，这里的终点流量是至少为 $k$ .

一点点小优化：由于我们已经枚举了答案，其实并不需要跑费用流，直接最大流就好了我不对劲

代码链接

孤岛营救

有一个 $n\times m$ 的方格，四个方向上相邻的两个单元格可能互通，可能有锁，可能不相通。有一些单元格中有钥匙。所有门分为 $P$ 类，打开同一类的钥匙相通，不同类的钥匙可能不同。求从 $(1,1)$ 到 $(n,m)$ 的最小时间，移动一格速度为 $1$ .

Solution

看到题完全不知道怎么网络流，数据范围很小倒是可以暴搜。真就不是网络流啊草 我还期待着有什么高妙建模呢TNT

直接状压钥匙，最短路就好了……

代码链接

航空路线

给定一张航空图，图中顶点代表城市，边代表直通航线，找出一条满足条件且途径城市最多的旅行路线。

1. 从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可以途径）
2. 除起点外所有城市只能访问一次

求出答案和路线。

Solution

拆点。对于两个拆分后的点，连 $x_1\to x_2$ ，流量为 $1$ ，费用为 $1$ 的边，除了起点和终点流量为 $2$ . 对于原图的边直接连出点和入点即可。当最大流等于 $2$ 时，最大花费减去 $2$ 就是经过的最大节点数。注意特判 $1\to n$ .

输入字符串是真的一点都不想写……

代码链接

汽车加油行驶

题面太长了自己看。

Solution

？$100\times 100$ 的网格图让我跑网络流？不存在的。这垃圾24题到底是谁出的啊。

代码链接

深海机器人

给定一张带边权的网格图和多个机器人（及其出发点和目标），每个人都向东或向北走，位置可以重合。每个边权由第一次经过的人拿走，计算最优方案下能获得的最大边权。$P,Q\leq 15$ .

Solution

写出数据范围就是要说明，极其小的网格图也是能跑网络流的（

终于出现了一道拆边题QWQ。显然，每条边都能经过无数次，但每条边都只能有一次贡献，那么可以拆成容量为 $1$ 费用为边权的边，和一条容量 INF 费用为 $0$ 的边。

拆完之后，多起点多终点，分别连 $S$ 和 $T$ ，跑最大费用最大流即可。

如果你 WA9 了不妨看看输入输出，挺坑人的。

代码链接

火星探险

在上一题中增加障碍物的限制，固定起点和终点，并且一定要全部到达。

Solution

？？？无聊。

代码链接

骑士共存

给定一个 $n\times n$ 的棋盘，有障碍，计算最多能放置几个互不攻击的马。

Solution

和方格取数类似，注意到能相互攻击的马一定是不同色的格子上的。

黑白染色之后，对于所有黑色点，向 $8$ 联通的格子连容量为 INF 的边，$S$ 向黑色点连容量为 $1$ 的边，白色点向 $T$ 连容量为 $1$ 的边，跑最小割即可。

为什么 $200\times 200$ 的网格图能跑网络流啊……不懂了哦，诶。

代码链接

最长 k 可重线段集

给定平面 $\text{xoy}$ 上 $n$ 个开线段组成的集合 $I$ 和一个正整数 $k$ ，从中选出 $S\in I$ 使得在 $x$ 轴上任意一点 $p$ ，$S$ 中与 $x=p$ 相交的开线段个数不超过 $k$ ，且长度和最大。

Solution

？这和“最长 k 可重区间集”有区别吗？并没有。

不过是当线段平行于 $y$ 轴的时候会出现自环，所以要先 $\times 2$ 然后再判断，最后离散化。

代码链接