《线性规划和网络流24题》小结
终于半看题解，半讨论地做完了网络流24题（除了Byvoid没做的那题还有最后两题不想做- -||），还是有点感触的，小小总结一下。
经典建模
最大权闭合图问题
- 从S到正权点连和点权一样的边
- 从负权点到T连-点权的边
- 其余按照原图连无穷的边
跑一遍最小割，正权点之和-最小割容量就是答案。引用Byvoid的话：
定义一个割划分出的S集合为一个解，那么割集的容量之和就是 (未被选的A集合中的顶点的权值 + 被选的B集合中的顶点的权值)，记为Cut。 A集合中所有顶点的权值之和记为Total，那么Total - Cut就是 (被选的A集合中的顶点的权值 - 被选的B集合中的顶点的权值)，即为我们的目标函数，记为A。 要想最大化目标函数A，就要尽可能使Cut小，Total是固定值，所以目标函数A取得最大值的时候，Cut最小，即为最小割。
输出方案的方法是：从S沿着非零流边跑一遍DFS，和S相连的点与和T相连的点就是两边的方案。
例题：
- prog82
有向无环图最小路径覆盖
- 每一个点拆成Xi和Yi两个点，连边
- 连边
- 对于原图边(u, v)，连边
跑一遍二分图匹配，答案就是顶点数-匹配数。
所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。 该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。 每增加一条匹配边，那么路径覆盖数就减少一个， 所以路径数 = 顶点数 - 匹配数。 要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。
方案就是从Xi出发，沿着零流边走到Yj，再从Xj开始往下走。所走到的点就是路径的点。
例题：
- prog83
- prog84
二分图（多重）匹配
连边
跑最大流就是最大匹配了。这个应该是很好懂了。
例题：
- prog85
- prog87
二分图点权最大独立集（点权最小覆盖集）
连边：
- 对于原图(u, v)，连接
跑一遍最小割，最小割容量就是点权最小覆盖集，总点权-最小割就是最大独立集。
1.prog89
经典方法
求值转判定
有些拆点的题目要根据答案来拆，这个时候就得枚举答案。一般来说枚举答案都是二分，但是对于网络流来说，可能朴素循环更好：
- 省去重复建图的花费
- 每次跑的时候相当于对上一次的补充，省去了一大堆重复的路径
- 一般答案不会很大，都是在100以内（尤其是要根据答案拆点的题目）
比如prog84。
对付限制
- 每一个点走一次：拆点，连边
- 每条边走一次：容量为1
- 没有限制：容量为INF
比如prog816就很经典。
拆点
除了上面对付每个点只能走一次的限制，拆点在阶段性很强的题目中，根据阶段拆点、连边，比如：prog813
特别地，经常可以拆成二分图：比如费用流非常经典的prog810，用X部的点表示干净的毛巾，Y部表示洗过的毛巾，接下来就很好转移了。
囤积流量
还是像prog810，需要囤积没用完的毛巾，那么就连边
此外，像prog819，搬东西只是暂存，连边
分层图
经常用位运算来分层，适合点数不是很多的题目。经常是最短路和BFS用的比较多。
福利
因为这套题目需要输出很多的方案，而方案又不唯一，所以我就写了好几个Cena的自定义校验器（没有全部都写）。另外根据Byvoid说的，数据有错误，我也修改了。干脆连自己的程序一并打包传上来。
包含了我自己的程序、自己写的校验器、Byvoid的整理的题解。