这是本文档旧的修订版！
目录
图论 3
网络流经典例题
方格取数问题
题意
给定一个 $n\times m$的方格图，每个方格中都有一个正整数。
现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。
题解
由于每个方格限制较少，故考虑利用限制建边。
考虑先取所有方格，再删去权值和最小的一组方格，使得剩下的方格没有公共边。
问题转化为建立一个模型，支持以下操作：
- 支持删除元素，且删除代价为元素点权
- 保证操作最优或者操作可逆
- 最终状态为剩余元素没有冲突
发现可以将方格进行黑白二染色，显然同色方格间没有限制不连边，所以可以得到二分图。
从源点向每个黑格连一条边，容量为黑格点权。如果删去该边，表示删除黑格。
从白格向汇点连一条边，容量为白格点权。如果删去该边，表示删除白格。
最后从黑格向有冲突的白格连一条边，容量待定。
问题转化为最小割问题，事实上图不连通等价于没有从源点到黑格，黑格经过冲突边到白格，白格再到汇点的路径。
这又等价于不会同时选择冲突的黑格和白格，即最终的目的。
然后需要保证最小割只选择源点到黑格的边和白格到汇点的边，所以把黑格向有冲突的白格连的边容量设为 $\inf$。
最后求最小割，答案为点权总和减去最小割。
航空路线问题
题意
给定 $n$ 个点，$m$ 条边。规定 $1$ 号点为起点，$n$ 号点为终点。
要求输出一条从起点经过终点再回到起点的路径，要求路径上的节点编号先单调增，再单调减，且路径上无重复节点。
如果存在多条路径，输出任意一条最长的路径。
题解 1
首先问题可以转化为从起点开始走两条不相交的路径。
每个点可以走一次且记一次贡献，所以考虑拆点并连一条容量为 $1$ 权值为 $-1$ 的边。
注意起点终点会走两遍，但贡献只计算一次，所以需要额外连一条容量为 $1$ 权值为 $0$ 的边。
然后从汇点连一条容量为 $2$ 的边到起点，从终点连一条容量为 $2$ 的边到汇点，保证存在两条路径。
最后根据输入的边连接网络流的相应点即可，注意这些边不一定只会走一次(例如 $n=2$ 且起点终点连通的情况)，所以边的容量设为 $2$。
题解 2
发现可以 $\text{dp}$ 解决，时间复杂度 $O(nm)$。
最长 $k$ 可重区间集问题
题意
给定 $n$ 个开区间，要求选取若干个区间，使得 $X$ 轴上每个点最多被覆盖 $k$ 次。
问在所有可能方案中，选取区间长度和最大值为多少。
题解
很自然想到每个点最多覆盖 $k$ 次可以理解为 $X$ 轴上流量最大为 $k$，而长度和最大可以理解为费用流。
首先考虑到费用流没有点权，考虑将一个区间拆成左端点和右端点，两端点间连一条容量为 $1$，费用为区间长度相反数的边。
没有相交的区间不存在约束，考虑在靠左区间的右端点向靠右区间的左端点间连一条容量无穷大且费用为 $0$ 的边，表示可以同时选择。
而有相加区间的之间则不连边，使得两个区间竞争来自源点的流量，相互约束。
然而按上述方案连边，边的数量可能达到 $O(n^2)$，难以接受。
考虑将点离散化，分配到 $X$ 轴，在 $X$ 轴所有相邻点间连一条容量为无穷大(其实 $k$ 就够了)，费用为 $0$ 边。
对每个区间，仍然按上述方案连边。最后从源点连一条容量为 $k$ 的边到最左端点，从最右端点连一条容量为 $k$ 的边到汇点，跑费用流即可。
拓展
如果题目把开区间改成闭区间，拆点的时候当作 $[lef,rig+1)$ 处理就行。
最小路径覆盖问题
题意
给定一个 $\text{DAG}$，求最小的不相交路径集，使得每个点恰好属于其中一条路径。(允许路径长度为 $0$，此时路径仅覆盖一个点)
题解
先用 $n$ 条长度为 $0$ 的路径覆盖 $n$ 个点，然后考虑合并路径。
将每个点拆成入点和出点，易知每个入点/出点最多被合并一次，否则有两条路径相交。
从源点连一条容量为 $1$ 的边到每个入点，从每个出点连一条容量为 $1$ 的边到汇点，则可以满足上述的合并次数限制。
最后，对每条边，从入点连一条容量为 $1$ 的边到出点，表示以入点结束的路径可与以出点开始的路径合并一次。
最后需要合并次数最多，跑最大流即可。最小路径覆盖为节点数减去最大流。
关于路径打印，只要在求完最大流后跑残量网络即可。
最长不下降子序列问题
题意
给定一个正整数序列 $x_1,x_2,\cdots x_n$。
- 计算其最长不下降子序列的长度 $s$
- 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列
- 如果允许在取出的序列中多次使用 $x_1,x_n$，则从给定序列中最多可取出多少个不同的长度为的 $s$ 不下降子序列
题解
第一问考虑 $\text{dp}$ 求出以第 $i$ 个数结尾的最长序列长度。
第二问先考虑只允许使用一次这个限制条件，只需要把每个点拆成入点和出点，然后连一条容量为 $1$ 的边即可。
接下若满足 $j\lt i,a_j\le a_i,\text{dp}_j+1==\text{dp}_i$，则连一条 $j\to i$ 的容量为 $1$ 的边。
最后考虑从源点向 $\text{dp}_i==1$ 的点连一条容量为 $1$ 的边，从 $\text{dp}_i==s$ 的点向汇点连一条容量为 $1$ 的边。
最后跑最大流即可求出第二问答案。
对第三问，考虑把第 $1,n$ 个点的入点和出点的连边容量改为 $\inf$，同时把从源点到第 $1$ 个的连边的容量改为 $\inf$。
如果 $\text{dp}_n==s$，还需要把从第 $n$ 个点向汇点的连边的容量改为 $\inf$，然后重新跑一遍最大流。
但实际编程中不需要修改边，额外添加边即可。同时也不需要重新跑最大流，在残量网络上跑最大流然后累加上第二问答案即可。
需要注意 $s=1$ 的特例，题目需要求不同的不下降子序列就是为了防止此时答案为 $\inf$ 的情况。
