二刷 开坑
测评利用LOJ（一刷时候还在LJOJ上 好怀念 但是当时学得不扎实，基本上都只是看懂题解拉板子完成任务罢了）
6000 6001等为loj题号，题面参考loj，不再简述题意。
1. 6000 搭配飞行员
二分图匹配
2. 6001 太空飞行计划
最大权闭合子图的裸题
3. 6002 最小路径覆盖
最小路径覆盖的模板题
4. 6003 魔术球
首先看完题目考虑贪心。举例子发现没有不符合的，直接贪心AC。
从网络流方向考虑，列出一些情况之后可以把它们往图论方向靠。可以发现，如果把和为平方数的数之间，从小数向大数连一条单向边，那么其实这道题就被转化成了最小路径覆盖问题。但是问的是最多多少个，因此无法直接求解。可以枚举答案，一步一步添加对应的边，每次求最大流（由于之前操作中许多边已经被流完，相当于求增广路已经求了一半，而现在显然是可以继续求的(sap需要清空dis等数组)，所以复杂度是对的）。
5. 6004 圆桌聚餐
最基础的最大流建模 二分图多重匹配
6. 6005 最长递增子序列
AC的错误代码
子问题1：最傻的n方暴力即可。设答案为ans
子问题2：拆点建图。把一个点拆成ans个点，表示路径的第i个是该点的情况。从S向第一层的点连容量为1的边，从ans层的点向S连容量为1的边，在每一层内从每个左边的小点向右边的大点连容量为1的边。跑最大流即可。
子问题3：将子问题2中S连出、T连入的边均改成流量inf就对了。但是这个显然是错的吧。2 1 3 4 1最多是3，应该能拿出两个，我这个只能出1。然而过了。
正解
子问题2中一个点只需要拆成一个入点和一个出点。在入点和出点之间连容量为1的边。
若子问题1中求得的f[i]表示以第i个点结尾的最长递增子序列，那么显然所有的长度为ans的序列都从f[start]=1处开始，到f[start]=ans处结束。且从f[start]=1处开始到f[start]=ans处结束的所有f[x]逐个递增的子序列一定为长度为ans的递增子序列。
因此可以从S向所有f[i]=1的入点连容量为1的边，从所有f[i]=ans的出点向T连容量为1的边。同时，将所有f[i]逐个递增且可以到达的点之间连边。显然最大流的流量为可走的路径数。
子问题3只需将
!!!!!!!! 写到这里我才发现我读错题目了
原来题目里面不是把所有的流量限制都取消，而只是把1和n的取消
我是sb
那这道题做完了
7. 6006 试题库
简单最大流建模
8. 6007 方格取数
二分图最大点权独立集 的模板题
9. 6226 骑士共存问题
二分图最大独立集，上面这道题的弱化版。但是建模更加隐蔽一些，容易想不到骑士的二分图特性。
10. 6015 星际转移
注意到数据范围极小。枚举时间，把每个空间站拆成时间个点，加当前时间的边，判断是否能转移成功。转移成功了输出当时的时间即可。
11. 6008 餐巾计划
可以建二分图，一边表示每一天的没用过的，一边表示用过的。乍一看可以把每天的没用过的朝用过的连r[i]的边，把用过的朝后面洗完的那几天连边。但是这样就无法靠最大流来限制每天必须用r[i]个碗，也不方便引入买新碗的操作。那么考虑可以把r[i]个碗硬塞给“用过的”点（从S出发给它连费用0的边），让r[i]个碗从“没用过”拿走（从T流出），洗衣则是从“用过的”向后几天的“没用过”连有费用的边，同时还需要从S出发卖给“没用过”一些新碗（容量inf）。可以发现，这样的图必定是可以把流量跑满的，那么我们就完成了用流量来强制“用”碗的步骤。
12. 6010 数字梯形
最大权不相交路径 裸题
13. 6014 最长k可重区间集问题
首先离散化。对于离散化完的点，从S向第一个点连容量为k费用0的边，对每两个相邻点之间连容量大于等于k费用0的边，从最后一个点向T连容量大于等于k费用0的边，对每个区间的端点，连费用为(-长度)的容量为1的边。
向第一个点连容量k的边，表示最多有k重。每两个相邻点连边，表示如果不选择任何区间，答案将是0。对于区间端点，容量为1显然是为了保证该区间不被选择多次。总的来看，建图之后形成了一张分层图，每一层的总流量都为k，费用0的边以外的其它边的总流量即为在当前层选择的区间的数量。
14. 6227 最长 k 可重线段集问题
和上面这道几乎一模一样的题目
唯一的区别就是会出现起点和终点在同一个点的情况。那么其实可以拆点，把自己指向自己的边改成自己指向自己和下一个点的中点的边，把其它的边改成从起始点前的中点出发即可。
15. 6011 运输问题
基本建图
16. 6012 分配问题
基本建图
17. 6013 负载平衡
基本建图
18. 6224 深海机器人问题
二维基本建图
19. 6122 航空路线问题
建图很基础，但是输出方案比较恶心
输出方案的过程中容易出小错误。同时，还要考虑无解的情况。按照我的建模方法，并不是费用流求出来0就是无解，而是最大流求出来0才是无解。
20. 6225 火星探险问题
建图仍然比较基础，障碍物设成费用q*p即可。但是输出方案仍然比较恶心。
可以判一判那些流量inf的边是不是inf，每处理出来一条路就把这条路的流量都+1，加回去直到变回刚开始的inf。
后记
24题里面剩下的题目就是分层图最短路和一道假题了。看啥时候心情好来补分层图最短路吧。不过应该先学学上下界网络流？