一些内容在另一篇博客
有的时候要保证最大的情况下，费用尽可能优。
就要用费用流了。
目前所涉及的费用流，都是在最大流的前提下
所以，当题目可以转化成，在保证。。。的情况下，最优化。。。
也许就可以尝试费用流了。
（同样意味着选择，
最小割没有什么最大流的前提，可以没有什么地，割掉一些边即可。
但是，每条边必须割掉，不能“割一部分”，对于一些可以剩下的模型就捉襟见肘了。
）
用EK。因为dinic不能保证流出来的是最优代价的。
至于为什么每次贪心选择最优的路径，最后就是最优的，可能的原因是，因为有反边，所以自带反悔自动机功能。贪心没有问题。
可以延伸出来一个结论：
最短路费用流，当前费用是所有能够到达当前总流量的所有费用中最优的一个。
（伪证：
因为贪心成立。还没有听说过哪个贪心不是局部最优解，却是全局最优解的2333
）
例题：
方格取数、晨跑。
拆点费用流即可。
修车，美食节
拆点费用流。
边权设计：
反过来考虑每个人站在某个位置，对后面的人等待时间产生的影响。
第j个阶段，意味着后面还有j个。这样，贡献就只和自己有关系了。
必要的时候动态加边。
倍数关系，这个倍数关系还是质数。
那么，这两个数的质因子一定相差一，差的那个质因子就是这个质数。
所以，把数按照质因子个数奇偶性分成左右两类
左部点右部点自己之间不会有配对。
左部右部点之间，如果成倍数关系，并且一个是另一个质因子个数+1，那么连边流inf，费c1*c2。
左部点和S，连流b费0
右部点和T，连流b费0
这样，每个流就是一个配对。
至于
“在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。”
费用流的特点是，
“可以保证当前的费用永远是当前流量下最优的”
所以，如果当前总费用<0
那么就可以停止了。因为之后，流量更大的话，费用也不可能更高。
看似费用流。
其实发现，Bob一定选择最大的流量*p
所以，Alice要使得所选择的最大流的最大流量最小。
二分判断即可。
注意，边最大流量不一定是整数。因为可以均摊成小数变得更低。
eps 1e-5即可。
upda：2019.2.11
由于贪心成立，
所以，费用流的一个优秀的性质是，当前选择的，就是当前的最优解
在一些基于费用流的剪枝中，经常会用到费用单调的性质
即每一次的费用都大于等于上一次
这个可以证明
upda：2019.6.11
无源汇上下界最小费用可行流，消负环？
用循环流填充负环。
法一：spfa时候找到负环，不断找pre，整个负环的流量就是容量最小的边。暴力填满
法二：
先砍掉下界。但是先不处理下界带来的盈余流。
先处理负循环流
类似上下界网络流，钦定负边直接流满，注意这里可以反悔！也就是反向边有流量！
超级源汇，最小费用最大流，处理每个点关于负边产生的盈余流。然后就把负循环流填满了。
然后，再和上下界可行流一样，
把干掉下界带来的盈余流，超级源超级汇，最小费用最大流处理掉。
至于有源汇的循环流有什么实际意义，，，，我也不清楚
反正在无源汇上下界中，只有循环流了。