网络流 23 题做题记录
所以网络流是毒瘤建模题吗？
爱了爱了。
单价，显然是最小费用最大流。
考虑这道题怎么建模。
用费用流，餐巾条数用流量替代，然后流满即满足条件。
剩下的就是最小费用了，考虑如何建模能够使得所有情况都被考虑到即可。
首先本题没有源汇，故显然应该建立超源超汇。
考虑获得餐巾的几种方式。
获得干净毛巾：可以通过快洗、慢洗、买。
由于脏毛巾数量亦有限，故同样需要考虑。
获得脏毛巾：可以通过上一天继承、以及每一天用完之后额外获得。
于是我们把每一个“天”拆成两部分，一部分处理干净毛巾，一部分处理脏毛巾。
先考虑干净毛巾。
然后先从简单的开始建模，显然我们应该要满足条件。考虑每一天都交付量为 $a_i$ 的干净毛巾，故应每一天的干净毛巾结点连一条边到汇点，费用为 $0$ 流量为 $a_i$ 。
然后每一天我们必然会额外获得 $a_i$ 的脏毛巾，故从源点连一条流量为 $a_i$ 费用为 $0$ 的边到每一个脏毛巾结点。
然后考虑毛巾之间的转化。
首先是购买，由于购买无限量，我们从源点连一条流量为 $\inf$ ，费用为 $p$ 的边到所有干净毛巾结点。
然后是洗，可以把脏毛巾在一定时间后转化为干净毛巾，故对于每一个脏毛巾结点，对于每一种方式连一条流量为 $\inf$ ，权值为对应代价的边到对应天数以后的干净毛巾结点上。
最后是脏毛巾的继承，上一天的脏毛巾可以无限继承（不会发臭也不会腐烂），所以从每一天的脏毛巾结点连一条流量为 $\inf$ 权值为 $0$ 的边到后一天的脏毛巾结点。
然后一遍 $\text{MCMF}$ 就行了。
这就是网络流的美妙所在，和数据结构一样清晰而复杂，简单又困难，扑朔迷离，变化无穷。
板子题，直接二分图匹配即可。
网络流中最大闭合权子图转最大流的板子。
但我们从建模的角度分析。
首先，我们发现直接去最大流会有负权边，十分难搞，又不是单位价格不好费用流。
所以我们考虑负权边怎么处理。
考虑建成正权然后改一改建模。
然后我们考虑怎么改建模。
显然最大流是不行的，改成最小割。
那么我们认为一次 割 是一次 亏损 ，然后那么 最小割 就是 最小亏损 了，此时我们用所有 实验的贡献之和 减去最小割就是答案。
那么考虑亏损会怎样产生。
- 不做某一个实验，但可以不买某一些仪器
- 买必须买的仪器，但可以少不做一些实验。
于是考虑建立超源超汇，源点向每一个实验连边，每一个仪器向汇点连边，边权均为其权值。
然后对应的实验向仪器连容量为 $\inf$ 的边。
那么前者可以通过断 源点-实验 边处理，后者可以通过断 仪器-汇点 边处理。
前者表示不做某个实验，后者表示要买某个仪器。
那么当源汇不连通时，显然每一个 被选的 实验所对应的仪器都被断了即被选了，剩下的实验所对应的仪器就 可能 没有被选，但不做实验本身是亏的。
于是得到了答案。
然后考虑怎么输出方案。
由于我们使用的是 Dinic 算法，最后一次网络流事实上并没有更新最大流。
此时被分到层的所有实验结点显然没有被割掉，而所有被分到层的仪器结点显然被割掉了，故输出所有分到层了的点即可。
挺基础的一道建模。
显然每一张卷子要选对应道题，考虑建立超源超汇，源点向每一张卷子连边，容量为对应的题量。
每一张卷子向它所能容纳的题目连一条边，容量为 $1$ ，表示选择了这道题。
然后每道题最多被选择一遍，故每一道题向超汇连边，容量为 $1$ 。
然后跑一遍最大流，能选满的话 $maxflow=m$ ，否则 $No~solution$ 。
输出方案传统艺能即可。
这道题题解都放在题面里面了。。。
但它确实是一道网络流的经典问题。
首先我们考虑最小路径覆盖本质上是什么。
假设我们把一条路径看成一个 点集 的话，那么其实就是点集个数。
若我们称把一个点扔一个 已有点集 为一次 “合并” 的话，那么其实就有 最小路径覆盖=总点数-最大合并次数 。
那么现在考虑怎么求这个最大合并次数。
首先显然每一个点最多被合并一次，且最多合并一个点。
那么就考虑建超源超汇，然后拆点，对于源点向每一个入点连一条容量为 $1$ 的边，对于每一个出点向汇点连一条容量为 $1$ 的边。
然后考虑一个点能不能合并另一个点，故对于原图中的每一条边 $(u,v)$， $u$ 的入点向 $v$ 的出点连一条容量任意的边，只要值为真即可。
显然连 $1$ 比较好，因为容易输出方案。
我们只需要考虑每一个点 合并 了哪一个点，然后根据最大流跑出来的结果输出即可。
首先注意到我们在求完最大流之后是可以继续加边，继续求最大流的。
那么这道题就做完了。
首先我们每一次扔一个新的点进去，那么它必然只会有两种情况。
- 放在一根新的 柱子 上
- 放在已有的球上
首先我们不考虑第一种情况。
那么对于第二种情况，我们需要保证每一个球上面最多只有一个球，显然要套路拆点，一个点提供贡献一个点收集贡献。然后每一个出现过的，能与当前新点产生关联的点连一条边。
然后跑一遍最大流，看看最大流有没有变大。
如果没有，说明这个新点流不动了，那么新建一根珠子，显然这里若产生新的贡献还要再跑一遍网络流很不划算，干脆不建边，其实也是对的。
然后输出方案什么的有手就行。
这道题给我们的最大启发一方面是网络流可以不断加边，另一方面是并不是所有限制条件都需要在网络流建出来的图中体现。
很巧妙的一个分层图思想。
首先第一问显然可以动态规划解决，然后处理出了一个 $dp$ 数组以及答案。
然后我们考虑对于这个序列分层。
对于每一个 $i$ ，对于每一个 $j>i$ 且 $dp[j]=dp[i]+1$ 且 $a[i]\le a[j]$ ，那么 $i$ 才可能会与 $j$ 存在于 同一最长不降子序列中，且刚好是相邻的两项 。
否则显然不可能。
于是我们利用 $dp$ 数组进行了分层。
剩下的就好办了，对于只能使用一次的限制考虑拆点，然后第三问稍微改一改就行，显然最后跑最大流跑出来的结果就是不同的最长上升子序列的条数。
可能实现上细节有一点多，比如特判 $n=1$ 什么的，这个到时候自行判断。
11、P2774 方格取数问题
还是结论题。
最大独立集=总点数-最小点覆盖，最小点覆盖=最大匹配数
然后就好了。
然而这道题带权。
一种 naive 的思路是把每一个点全部拆成若干个点，然后暴力连边。
这样子显然是错的。
然而显然我们拆出来的这些点又可以合并成一个点，那么不妨认为一个点代表了 $a_{i,j}$ 个点。
那么一种方法是原先与源汇连的边的流量由 $1$ 改为 $a_{i,j}$ ，那么等效为这一个点包含了 $a_{i,j}$ 个点，然后就没有然后了。
一遍最大流然后套结论即可。
12、P3254 圆桌问题
目前有一个思路是这样的：
首先对于每一个单位，由源点连过来容量为 $r_i$ 的边，然后它向每一个餐桌连容量为 $1$ 的边，最后每一个餐桌向汇点连 $c_i$ 的边。
然后似乎就满足所有限制条件了。
一遍最大流+输出方案即可。
13、P3355 骑士共存问题
网络流非常经典的问题。
考虑建二分图。
对于所有互相冲突的连边。
然后似乎就没有然后了。
根据 最大独立集=总点数-最小点覆盖，最小点覆盖=最大匹配数 。
然后一遍二分图匹配即可，知道结论就是大板子题。
二分图匹配的具体实现就不多说了。
20、P4013 数字梯形问题
板题，三个费用流板子。
第一个点边都有限制，故点拆点，边限流。
第二个点无限制，不同拆点，边限流。
第三个都没有限制，故都不限制。
然后就做完了。
注意源点连出来的的所有点流量只能为一。
21、P4014 分配问题
板子题。
直接二分图最大匹配最小匹配两边费用流即可。
22、P4015 运输问题
板子题。
直接超源超汇与对应点建边确定 限制，中间暴力连边给出 “给货物” 的通道即可，由于无限给所以流量 $\inf$ 。
23、P4016 负载平衡问题
我们认为流量是货物，那么就考虑一个点从源点得到了 $a_i$ 的货物，但是要给汇点的货物数是 $\overline a$ ，所以考虑最小费用最大流，利用最大流满流来打成限制条件。
剩下的最小费用，考虑只有一种情况就是这个点向前后两个结点提供货物即流量，而提供的量是无上限的，故两两之间 互连 流量无限大，费用为 $1$ 的边即可。
然后一遍最小费用最大流即可。