模拟费用流/可回退贪心/wqs 二分

方法 1

用数据结构快速维护寻找增广路的过程。

可以用这种方法的问题中增广路一般都很短，或者是增广路中实际有意义的部分很少，有时可以利用增广路无环这一条性质来抓住关键点。

这其实就是可回退贪心。

方法 2

对于一个有源汇的图，令 f(x) 表示流量为 x 时的最小费用，那么 f(x) 一定是一个凸函数。

我们可以用一条斜率为 k 的直线切这个凸壳，即流量每增加 1，费用就会减少 k。

这便是 wqs 二分的思想。

这样做的好处是可以用 O(\log V) 的代价去掉总流量的限制。转化后的问题需要视情况而定。

方法 3

以某种顺序依次加入图中的每一个点，考虑当前加入一个点对决策的影响。

此时就需要分为增广路和增广环两种情况分别考虑。类似方法 1，使用数据结构维护。

特别注意增广环既有可能是 S\rightarrow S 也有可能是 T\rightarrow T。

这种方法单独使用不能处理对流量有限制的情况，但可以结合方法 2 解决这个问题。