Sengxian's Blog

终于做完了，我是在 COGS 上面做的，首先来几点吐槽：

• COGS 居然只能提交文件，对于我这种目录深的，表示很不习惯。
• COGS 输入输出用文件，这个不评论了，各有喜好。
• COGS 对网络流24题收录不全，仅仅只有 21 道题
• 网络流24题中，有些题描述很不严谨，甚至连范围都没有给。
• 网络流24题中，有几题不能做，有几题数据有问题，还有很多题几乎就是水题，还有几题就不是网路流。

但不可否认，还是有几题是比较好的，建议有选择的做，下面一一点评（借用一下 BYvoid 的表）

只对我认为比较好的题来题解：

最小路径覆盖问题 - 3

构造二分图，把原图每个顶点 $i$ 拆分成二分图 $X$，$Y$ 集合中的两个顶点 $X_i$ 和 $Y_i$。对于原图中存在的每条边 $(i,j)$，在二分图中连接边 $(X_i,Y_j)$。 新建源汇 $s, t$，$s$ 向每个 $X_i$ 连边，$Y_i$ 向 $t$ 连边。然后把二分图最大匹配模型转化为网络流模型，求网络最大流。
最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数。沿着匹配边查找，就是一个路径上的点，输出所有路径即可。
我们认为 $X$ 集合代表每一个点的出点，$Y$ 集合代表每一个点的出点，由于要求的是路径的集合，我们先研究单条路径。显然，每个点属于且仅属于一条路径，那么意味着出来路径的起点和终点，每个点都有唯一的前驱和后继，那么从 $X_i$ 出发的边指向后继，从指向 $Y_i$ 是 $i$ 的前驱，所以原先 $(u, v)$ 的边，就变为了 $(X_u, Y_v)$。而起点的前驱是 $s$，终点的后继是 $t$，由于每个点都有可能是路径端点，所以从 $s$ 向每个 $X_i$ 连边，$Y_i$ 向 $t$ 连边。
注意到每个条路径只有一个终点，而除去终点外的所有点 $X_i$ 均被匹配，所以有多少个未被匹配的 $X_i$，就有多少条路径。

总结：对于路径问题，通常将点拆为入点和出点，利用二分图的性质。

魔术球问题 - 4

转换思路，不好求有 $n$ 个柱子时可放的球数量，我们求可放 $n$ 个球时的最小柱子数量，注意到同一个柱子上球的标号递增，所以可以转化为最小路径覆盖问题。
枚举答案 $T$，在图中建立节点 $1,2,...,T$。如果对于 $i<j$有 $i+j$ 为一个完全平方数，连接一条有向边 $(i,j)$。该图是有向无环图，求最小路径覆盖。如果刚好满足最小路径覆盖数等于 $n$，那么 $T$ 是一个可行解，在所有可行解中找到最大的 $T$，即为最优解。可以顺序枚举 $T$ 的值，当最小路径覆盖数刚好大于 $n$ 时终止，$T-1$就是最优解。
最小路径覆盖数随球的数量递增不递减，满足单调性，所以可以顺序枚举答案（或二分答案），对于特定的答案求出最小路径覆盖数，一个可行解就是最小路径覆盖数等于 $n$ 的答案，求出最大的可行解就是最优解。本问题更适合枚举答案而不是二分答案，因为如果顺序枚举答案，每次只需要在残量网络上增加新的节点和边，再增广一次即可。如果二分答案，就需要每次重新建图，大大增加了时间复杂度。

总结：有些时候要转换思路，寻求问题容易求解的形式，转化为判定性问题，而判定问题有时更适合枚举答案，在原图上加点。

最长递增子序列问题 - 6

用 $O(n^2)$ 的动态规划求出 $f[i]$，表示以第 $i$ 为结尾的最长上升序列的长度，$\max f[i]$ 就是最长上升序列长度，记 $K = \max f[i]$。
第二问，问的是同时取出，每个数只能用一次！由于最长上升子序列有阶段性的特征，即 $f[i]$ 的值为阶段，所以流量的流动，就像阶段的转移，考虑建图：

1. 把序列第 $i$ 位拆成两个点 $i_a, i_b$，从 $i_a$ 到 $i_b$ 连接一条容量为 1 的有向边。
2. 建立附加源 $s$ 和汇 $t$，如果序列第 $i$ 位有 $f[i]=1$，从 $s$ 到 $i_a$ 连接一条容量为 1 的有向边。
3. 如果 $f[i]=K$，从 $i_b$ 到 $t$ 连接一条容量为 1 的有向边。
4. 如果 $i < j$ 且 $A[i] < A[j]$ 且 $f[j]+1=f[i]$，从 $i_b$ 到 $j_a$ 连接一条容量为 1 的有向边。

显然，拆点的目的是为了限制每个点只能用一次，对于 $f[i] = 1$ 的点，是阶段的开始，$f[i] = K$ 的点，是阶段的结束，而第 4 条，即为阶段的转移，一束流量为 1 的流，只有经过 $K - 1$ 次转移，才能到达汇点，而每一束到达汇点的流，均一一对应一个 LIS。因此第二问的答案就是本图最大流。
把 $(1_a, 1_b)$，$(n_a,n_b)$，$(s,1_a)$， 这三条边以及如果 $f[n] = K$ 的话，$(n_b,T)$ 的容量修改为无穷大，再求一次网络最大流，就是第三问结果。
当然数据有问题，建图应该是对的。

总结：有的时候流量流动的意义非常重要，它可能代表着阶段的转移，这种阶段图的思想很重要。

方格取数问题 - 9

很妙的建图，将棋盘黑白染色，发现只有不同颜色的格子，才可能冲突。将每个格子看作一个点，如果我们将有冲突的格子之间连边的话，会发现这是一个二分图。

1. 将黑点放在 $X$，白点放在 $Y$。
2. 增加源 $s$ 和汇 $t$，将每条二分图的边 $(u, v) u \in X$ 替换为容量为 $\infty$ 的有向边 $(u , v)$。
3. 对于 $X$ 集中的每个点 $u$，从 $s$ 向其连一条有向边，容量为该点的数值；对于 $Y$ 集中的每个点 $u$，从 $u$ 向 $t$ 其连一条有向边，容量为该点的数值。

不难发现，此图的最小割就是原图的最小点权覆盖集，而二分图最小点权覆盖集的补集就是二分图的最大点权独立集。
有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。

总结：经典模型的学习是很重要的，要理解，更要会应用！

餐巾计划问题 - 10

一开始自己做的时候，不知道将每一天用完的餐巾这股流弄到那里去好，如果流向汇点，那么就无法送去洗，如果送去洗，又无法保证到汇点满流，于是只好看题解。
这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。
在每一天的餐巾需求为 $r_i$ 的情况下，如果满足，必定余下 $r_i$ 个餐巾可以任意处置，所以我们新增流而不是将已经用的流流回。
把每天分为二分图两个集合中的顶点 $X_i$，$Y_i$，建立附加源 $s$ 汇 $t$。

1. 从 $s$ 向每个 $X_i$ 连一条容量为 $r_i$，费用为 0 的有向边。表示每天用完的餐巾
2. 从每个 $Y_i$ 向 $t$ 连一条容量为 $r_i$，费用为 0 的有向边。表示每天必须满足的需求
3. 从 $s$ 向每个 $Y_i$ 连一条容量为 $\infty$，费用为 $p$ 的有向边。表示购买餐巾。
4. 从每个 $X_i$ 向 $X_i+1(i+1\le N)$ 连一条容量为 $\infty$，费用为 0 的有向边。表示餐巾，是可以放着不洗存到下一天的。
5. 从每个 $X_i$ 向 $Y_i+m(i+m\le N)$ 连一条容量为 $\infty$，费用为 $f$ 的有向边。表示快洗。
6. 从每个 $X_i$ 向 $Y_i+n(i+n\le N)$ 连一条容量为 $\infty$，费用为 $s$ 的有向边。表示慢洗。

此图最小费用最大流即为答案。

总结：本题反映了分析一类问题的方法，分析问题的约束条件，分析问题的所有可能决策，从而有的放矢的建图。边，有时候意味着一种决策，我们利用网络流，来获得最优决策。新增流的手法也是很重要。

骑士共存问题 - 24

与 9 很类似，黑白染色，显然只有不同颜色的点才有可能冲突，不同的是多了障碍物。
我们屏蔽一切连向障碍物的边，求最大独立集，不难发现障碍物也属于独立集，从独立集中去除障碍物，由于我们建图的攻击关系是完全的（障碍物不攻击别人也不被攻击，其余的马会相互攻击），一定有剩下的部分是原图的最优解。

总结：学会一个模型，还要灵活应对模型的变体。