本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-10 18:17:11

P2756 飞行员配对方案问题

做法

将每个外籍飞行员向他对应的英国飞行员连一条流量限制为 $1$ 的有向边
然后设两个点 $s,t$，分别代表源点和汇点。
$s$ 对所有的外籍飞行员连流量限制为 $1$ 的边。
所有的英国飞行员都向 $t$ 连流量限制为 $1$ 的边。
然后跑最大流就行了

Code

还没写

P1251 餐巾计划问题

做法

最小费用流
因为最终流的大小肯定是固定的 $\sum_{i=1}^n r_i$，而且每天都可以购买最多 $r_i$ 餐巾纸，所以可以从源点向每一天连一条费用为 $0$，流限制为 $r_i$ 的边。

而考虑到快洗部，第 $i$ 天都可以将一些脏餐巾用 $f$ 的代价洗了之后送到第 $i+m$ 天，所以可以从第 $i$ 天向第 $i+m$ 天连一条费用为 $f$，流量限制为 $\infty$ 的边。

慢洗部同理。

对于延期送洗，从第 $i$ 天 向 第 $i+1$ 天连一条费用为 $0$，流量限制为 $\infty$ 的边。
最后，因为要统计结果，每天都要向汇点连一条费用为 $0$，流量限制为 $r_i$ 的边。
最后从源点出发跑最小费用流即可。

Code

没写

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

做法

数据范围小得离谱。

枚举时间作为答案。

枚举时间的时候的过程：

1. 上一个时间段的地球，月球，需要向这个时间段的地球连一条流量限制为 $\infty$ 的边作为时间的转移。
2. 同样的，上一个时间段的每个太空站也需要向这个时间段的太空连一条流量限制为 $\infty$ 的边作为时间的转移。
3. 对于太空船，将每个太空船上一个时间段所在的地方连向它下一个要去的地方，边的流量限制为 $h_i$。
4. 前三个步骤新建的边相当于构造了一张新的图，只不过每个点都与上一个时间段的图对应的点相连，为了保持一致还需要把之前图的点之间的边复制到这张新的图里。

Code

没写。

P2761 软件补丁问题

做法

这道题正解不是网络流。
可以发现，每个 bug 都只有修复好和未修复两种状态，可以看成 $1$ 和 $0$。而 bug 总数最多只有 $n (1 \le n \le 20)$ 个。

所以说可以状压。

可以将每个 bug 的状态压入一个数 $S$，S 的第 $i$ 位代表第 $i$ 的 bug 的修复状况。

这样 $S$ 就有 $2^n$ 种情况，可以看成 $2^n$ 个点。

初始状态（起点）是所有 bug 都未修复（$S$ 的每一位都是 $0$，$S =0$），最终状态（终点）是所有 $bug$ 都已经修复（$s$ 的每一位都是 $1$，$S = 2^n - 1$）

这些点之间的边，则是补丁。

每个点（状态），都可以通过任意一个当前点（状态)下可用的补丁走到另一个点（状态），代价则是这个补丁的耗时。

从起点跑最短路即可。

另外，由于边太多了，不能存储边。Dijkstra 的时候应当直接枚举每一个补丁行转移，而不是从当前点出发的边。

至于无解，如果起点无法到达终点，那么无解。

Code

没写

P2763 试题库问题

做法

每道题都可以对应很多个类型，而每个类型都共同对应了一套试卷，而题目要求每个类型都必须包含一定题目（数量题目给定）。

非常显然，就是最大匹配！。

对于这样的问题，当然是用匈牙利算法最大流来解决。

因为初始有 $n$ 道题目，从源点向每一道题连一条限制为 $1$ 的边。

因为每道题只能贡献一个类型，所以将每道题向其对应的每一个类型连一条流量限制为 $1$ 的边。

而每个类型都要向试卷贡献，设试卷为汇点，那么每个类型都向汇点连一条限制为 [该类型试题的需要量] 的边。

最后从源点出发跑最大流。

如果求得的最大流不是 $m$，那么说明无法给每个类型都分配足够的试题，无解。

如果有解，那么就要找每个类型所拥有的题目了。

因为网络流反向边的存在，可以从每个类型出发沿着反向边回到试题部分。

由于某道题匹配上了某个类型（就是说这道题到汇点的增广路径上有这种类型），那么它正向边限制就会变为 $0$，而反向边为 $1$（网络流的特性）

此时只要判断当前的反向边的限制是否为 $1$ 就行了，如果为 $1$ 说明这道试题属于当前类型。

另外要判断从类型节点出发的边是不是反向边，只要判断当前边的 $to$ 是试题节点就行了。

Code

没写。

P2764 最小路径覆盖问题

做法。

想一下，如果有 $n$ 个点，每个点之间都不连边，那么将会有 $n$ 条路径。

但是如果加上了一条边，那么路径数减一，将会有 $n-1$ 条路径。

也就是说，路径数等于总点数减去已经匹配到路径的点数（注：这里的点数不应该包括路径的起点）

此时问题转化成了最多有多少个点能匹配到路径里。

可以将每一个点 $i$ 拆成两个点 $a_i$ 和 $b_i$

由源点向每一个 $a_i$ 连一条流量限制为 $1$ 的边，代表可以从任一点出发。从每个 $b_i$ 向汇点连一条限制为 $1$ 的边，相当于将答案汇到了汇点。

另外对于题目给定的 $m$ 条边，假设 $i$ 和 $j$ 相连，那么从 $a_i$（代表起始） 向 $b_j$（$b_j$ 与汇点相连，用于统计答案） 连一条限制为 $1$ 的边。

解释：
这么连边就说明了从一个点出发顶多找到长度为 $2$ 的链，而真实的链肯定不会仅仅长度为 $2$，所以要从每个点出发才能找全。
另外由于每次都只会找到长度最多为 $2$ 的链（如果某个点不和其他任何点连通那么什么也找不到），这样最后产生的贡献最多为 $1$（就算这个点有好几个点相连，也只能和其中一个点形成链，因为和别的点再形成链答案也照样不变，画图可理解，再说了这些路径应该是顶点不相交的），所以源点到所有点连的边的限制只能是 $1$。
而每个点如果得到了流量那么说明这个点匹配上了，也仅仅说明这个点匹配上了，所以为了统计答案，每个点连向汇点的边的限制也只能是 $1$

至于路径输出，我的一个比较蠢的想法是爆搜记录每个点的后一个点，搜完了之后，对于每一个点暴力跳回最早的点输出。

Code

没写。

P2765 魔术球问题

做法

由于可以将相加起来是完全平方数的球放在一起，可以将将相加起来是完全平方数的球连边。

由于只能从最顶上放，而且是依次放编号为 $1,2,3,......$ 的球的，所以连边的时候应当从编号小的向编号大的连一条有向边。

$n$ 根柱子的存在，说明了要将这些球划分成 $n$ 份。也就是说将图划分成 $n$ 条路径。

问题转化为 $n$ 条路径最多能覆盖多少点。

解决这个问题，可以从小到大枚举每一个数，依次加进来。然后每次都一遍求当前状况下最少需要多少条边才能覆盖整张图(用上一道题的方法），记为 $cnt$，若 $cnt \ge n$ 那么退出，输出当前枚举到的数字减一。

关于输出每根柱子上的球编号：就是输出选中的 $n$ 条路径，从每个点顺着流满的边走。

Code

没写。

P2766 最长不下降子序列问题

做法

• 预先
  设以 $i$ 结尾的最长不下降子序列长度为 $f_i$
• 第一问
  暴力
• 第二问
  可以发现同一条不下降子序列之间的点是相互关联的，从前面的点走到后面的点 （这不废话吗）
  所以，按先后顺序，将前面的点与后面的点建边，因为一条路径上对答案的贡献最多是 $1$，所以边的流量限制为 $1$。
  另外，由于任意一点都可以作为一条不下降子序列的开头，所以从源点向这些点连一条限制为 $1$ 的边。
  另外，由于要汇集答案，而且只有长度为 $s$ 的不下降子序列才真正有贡献，所以从所有 $f_i = s$ 的点向汇点连一条限制为 $1$ 的边。
• 第三问
  因为在第二问中，每个元素只能使用一次，所以源点到它们的边限制只能是 $1$。但现在第 $1$ 个和第 $n$ 个元素可以多次使用，所以将源点和汇点与这两个元素的连边限制改为 $\infty$ 就行了

Code

还没写

P2770 航空路线问题

做法

虽然题目说先走到终点，然后再走回来，但是因为是无向图，所以可以认为题目实际上是找从起点出发的两条不同的到终点的路径。

这样起点和终点肯定都会经过 $2$ 次。

所以可以想到，可以设最大流为不同的路径数，费用则是经过的城市数，

所以应该跑最大费用最大流

因为起点和终点肯定都会经过 $2$ 次（从起点出发有两条路径到达终点），所以从源点向起点连一条费用为 $0$，限制为 $2$ 的边，从终点向汇点连一条费用为 $0$，限制为 $2$ 的边。

另外，对于普通的边，则是直接建一条费用为 $1$，限制也是 $1$ 的边。
注：刚才所说的 “点”，实际上应该是拆了之后的点。每个点都应该拆成一个入点 $x_i$ 和一个出点 $y_i$，设 $i$ 连向 $j$，那么应该是 $y_i$ 向 $x_j$ 连边。同时，为了把一个点拆成的两个点组合起来，应该让 $x_i$ 和 $y_i$ 之间连一条费用为 $0$，限制为 $1$ 的边（如果这个点是 $1$ 或 $n$，则限制应该是 $2$，因为要走两次）

对于解的判定，如果最大流小于 $2$，说明无法走到终点或者走到终点之后走不回来，无解。
但是最大流小于 $2$，不一定无解。因为起点可能直通终点，这样 起点 $\rightarrow$ 终点 $\rightarrow$ 起点 也是一个解，此时要进行特判。

最后，如果有解且起点不能直通终点，那么答案就是最大流减去 $2$，减去 $2$ 是因为起点和终点都访问了 $2$ 次。

Code

没写。

P3254 圆桌问题

做法

因为第 $i$ 个单位有 $r_i$ 个人，所以从源点向每个单位点连一条限制为 $r_i$ 的边。

因为每个桌子，同一个单位最多只有一人做，所以从每个单位点向每个桌子连一条限制为 $1$ 的边。

因为第 $i$ 个桌子最多 $c_i$ 人，所以从每个桌子点向汇点连一条限制为 $c_i$ 的边。

然后跑最大流

显然，如果最大流不等于总人数，那就说明无解。

如果有解，那么从每个单位出发沿着流满的路径找到对应的桌子输出就行了。

Code

没写。

P4016 负载平衡问题

做法

为了让它们平均，一定是多的给少的。

可以发现，最后结果只和它们与平均值之间的差有关。

所以，将平均值作为零，每个点的值变为 它原来的值减平均值。现在就是想要经过一定操作后使得每个点都变为 $0$

对于原值大于平均值的点，因为新的值是 它们原来的值减去平均值，所以从源点向它们建一条限制为 它们原来的值减去平均值，费用为 $0$ 的边，代表这些点在新图上的初始值。

对于相邻的仓库，互相连限制为 $\infty$，费用为 $1$ 的边，代表可以相互运。

对于原值小于平均值的点，因为这些点需要接收别的点的流量，会对答案产生贡献，为了统计这些贡献，需要从这些点向汇点建立一条限制为 平均值减去它们原来的值 的，费用为 $0$ 的边。

最小费用最大流

Code

没写。

P4015 运输问题

做法

千年一遇的水题，只写做法不解释

1. 从源点向每个仓库 $i$ 连一条容量为 $a_i$，费用为 $0$ 的边。
2. 从每个仓库 $i$ 向每个商店 $j$ 连一条容量为 $\infty$，费用为 $c_{i,j}$ 的边。
3. 从每个商店 $j$ 向汇点连一条容量为 $b_j$，费用为 $0$ 的边。
4. 最小费用最大流和最大费用最大流各跑一遍，输出答案。

Code

没写。

P4014 分配问题

做法

因为题目标签是网络流所以肯定是网络流算法
在这道题里，让求的是最小和最大总效益，也就是最小费用/最大费用流了，这也提示了将效益设为费用，同时最大流肯定就是总人数，所以边的流量跟人数有关。
这道题也是比较水的，下面只写做法，不解释：

1. 从源点向每个人连一条容量为 $1$，费用为 $0$ 的边。
2. 每个人 $i$ 向每个工作 $j$ 连一条容量为 $1$，费用为 $c_{i,j}$ 的边。
3. 每个工作再向汇点连一条容量为 $1$，费用为 $0$ 的边。

然后跑最小费用最大流/最大费用最大流

Code

没写。

P4011 孤岛营救问题

做法

发现 $P \le 14$，显然可以用二进制来存当前拥有的钥匙状态。
设 $i,j,k$ 表示到达 $(i,j)$，且钥匙状态为 $k$ 的最小花费。

暴力 bfs 即可。

Code

没写。