网络最大流

将流量作为路径，容量作为移动的限制

比如 [SCOI2007]蜥蜴这个题，就是典型的将蜥蜴的移动看成流量。

这是最经典的网络流做法。

这种问题可以处理：

边有限制，问最多几条路径。
最多的不相交路径（等价于第一种）

增量网络流/分层图

就是在上一次跑的基础上再新加若干点然后再跑网络流。

复杂度玄学，可以优化常数。

比如 P2754 [CTSC1999]家园 / 星际转移问题就可以这么做。

这种方法常常和枚举时间放在一起。

多个相同问题最优化个数

一个问题是相同的，我来好几个。可以建出一个问题的图，然后完成节点向 $T$ 连边，然后流量设成问题个数。

匹配问题

这个没啥好说，就是硬匹配。

但是注意建图的技巧。

二分最值

有些时候网络流可以通过最大流检验是否存在完美匹配这种方式来做一些 check 问题，于是就可以二分了。

P2402 奶牛隐藏

拆出入点转二分图

网络流比较喜欢处理二分图的问题。

拆出入点这个技巧有两个作用：一个是分层，为了区分我这个流量是从哪里过来的还是就是原本在那里的；还有一个作用就是限制点上的流量。

前缀限制转区间限制

CF628F Bear and Fair Set

直接看题，我在前缀上有一个限制，我把它差分成区间上的限制，然后就好办了。

假三分图

介绍一个概念叫三分图，普通三分图是 1,2,3 层都有连边的，但是假三分图 1,3 层没有连边，所以可以跑匹配。

网格图限制转二分图

经典结论，对于一个一行或一列的限制，可以转成一个二分图，行向列连边表示它们的交点处放了一个点。

这个玩意可以拓展，比如可以把一行分成若干段，每段互不影响这样。

相邻位置奇偶分类转二分图

就是名字，这个也太常见了。

流的线性性

自己创造的一个词，大概就是说，若干个流量的组合具有线性性，因此你可以把流做线性变换，得到的东西是等价的。但是可能具有更好的约束性质。

譬如 ZJOI2010 贪吃的老鼠，一开始正常的建图无法满足每个奶酪只被一只老鼠吃的限制，但我们把每个老鼠的速度差分之后，依然可以凑出所有老鼠的限制，但是此时我们可以通过限制中间的流量来使得每个奶酪只会收到一只老鼠的吃。（就是每个老鼠都只会吃这个奶酪 lim 次，然后这群老鼠的线性组合等价于原图的一只老鼠或者不到一只老鼠）

字典序最小

二分图求字典序最小有两种情况。

一种是匹配数量优先，一种是字典序大小优先（边权可能相等）。

考虑匈牙利算法。

匹配数量优先的时候由于是找最大匹配，而后考虑的左部点会影响前面，因此我们从后往前加入左部点，每次找最小的增广。

字典序大小优先的时候就比较好办，我们正着对于一个点，找所有边权尽可能小的点的增广路，如果有可行，那么连上这些边然后增广，这样可以保证即便反悔也是最优的策略。

有点像多步增广。

数据结构优化网络流建图

这个就和名字一样，没啥好说的。

最小割

总论

最小割主要处理类似“选了某个就不能选某个”的问题，这种问题通常若干个限制纠缠在一起比较难以处理，因此我们考虑用最小割来解决。

字面问题

就是求“最小割”，也就是我割掉某些边使得两个点不联通。

切糕模型

用来处理不同选择之间限制的好用模型。

基本上就是你 $S\to X\to T$，如果选 $X$ 那么就割掉 $S\to X$，如果不选 $X$ 那么就割掉 $X\to T$。

如果此时有一个限制，是 $X$ 不选 $Y$ 就必须不选，否则需要花费 $w$ 的代价，那么你连边 $X\to Y$ 就可以达到这个目的。

类似的可以拓展出多重选择。需要限制形如 $X$ 如果不选 $1\dots i$，那么 $Y$ 必须选 $i+1\dots n$ 否则就会有花费这样的情况。

还是要具体情况具体分析。