网络流 24 题做题笔记

· · 个人记录

先立个 flag，寒假结束前切完。

◈ 完成网络流 24 题（7/24）。

1 最大流

1.1 P2756 飞行员配对方案问题

链接

思路：

其实可以用二分图过，匈牙利之后就没了，网络流的话貌似是建图后在 DFS 中判断某一条是否被流量流过。

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

链接

思路：

首先判断是否有解，可以使用并查集。

分层图，我们将每一个时间节点视为一层图，通过枚举时间节点，一边跑 Dinic 一边建图。具体的，加入在 t 时刻某一飞船在 x_k，在 t+1 位于 x_{k+1}，那么我们将在第 t 层图中的点 x_k 向在第 t+1 层图的 x_{k+1} 连边。另外，我们需要建立多个起点（即地球），再建立一个超级源点连向它们，至于汇点可以固定（即不需要建立多个月球）。还有一个细节，因为是一边建图一边跑，需要在残量网络中跑网络流。

1.3 P2766 最长不下降子序列问题

链接

思路：

对于第一问，DP 解决（设以 a_i 结尾的最长不下降子序列。

对于第二问，我们可以对于所有的 f_i=1 的 i 与源点建边，流量为 1；对于所有的 f_i=s 的 i 与汇点建边，流量为 1；对于每一对 (i,j) 满足 j \ge i 且 a_j \ge a_i，由 i 向 j 连边，流量为 1。这样，最大流即答案，但是是错的，因为可能会出现一个点流过了 \ge 2 的流量，也就是该点出现在了至少两个最长不降子序列当中，不合法。我们可以将 i 分裂为 i_1 和 i_2，其中 i_1 保留 i 的所有入度，i_2 保留 i 的所有出度，再建边 i_1 \to i_2，流量为 1，达到了限制点的流量经过的效果。此时答案就是最大流。

对于第三问，将点 1 和 n 的点流经限制改为 +\infty，且源点向点 1 的边流量无限制（改为 +\infty），若 f_n=s 则也取消掉 n 至汇点的限制。再跑一边 Dinic 完事。

2 最小割

2.1 P2774 方格取数问题

链接

思路：

最小独立集经典问题。首先考虑将方格中相邻点全部建边，构成一个二分图，且二分图中边流量上限设置为 \infty。再将源点与所有左部点连边，汇点与所有右部点连边，流量上限为其在网格中对应权值。接下来跑最小割，没有被删掉的边与之对应点即被选中的点。

原理大致就是，因为若两点有连边（即在方格中相邻），两者至少有一个不选。我们建图方式会使两者出现让该图出现通路，在最小割中会选择删除两点与源点或汇点的连边中的至少一条，所以跑完最小割剩下的点就是可以选的点。

2.2 P2762 太空飞行计划问题

链接

思路：

不难发现，对于一场实验，要么做实验，要么将这一场要用的仪器全部不买（其它要做的实验用到的除外）。很容易想到建图方式，对于一场实验将其与之所有要用的仪器连边，构成一个二分图，其间容量为 \infty。再将左部点与源点连边，右部点与汇点连边，容量为该实验的收益或该仪器的价格。

跑最小割，答案就是所有实验的收益之和减去割去的边（若某实验被割，则说明该实验不用做，需减去；若某仪器被割，说明至少有一场实验要用到它，需要在收益中减去它的花费）。至于方案，就是所有与源点相连的边（若某实验被割，则该实验不需要做，且其所有相关的仪器若没有其它要做的实验用到，也不联通，即也不需要）

2.3 P3355 骑士共存问题

链接

思路：

方格取数 Pro MAX。

3 最小费用流

3.1 P1251 餐巾计划问题

链接

思路：

补充一下，餐厅一开始没有餐巾。

先拆点，将每天拆为白天和晚上，即 i 和 i'。然后我们根据题意：

至于为什么这样建边能满足限制条件，等会再说。

接下来考虑处理脏毛巾：

然后跑费用流即可。关于之所以限制条件能满足，是因为对于每个 i 和 i' 其所有从汇点流向它或它流向源点的路径中，至少有一条路径完全没有流量限制，所以剩下的那条路径一定会满流，而这条就是限制条件。