upd:现在不是了!rk1写的是网络单纯形，会学的会学的/ll
以下默认我们做的是最小费用循环流。\(C,U\)分别指费用和流量的值域。
网上找了一堆东西，最后找到了原论文，Finding Minimum-Cost Circulations by Successive Approximation，可以在这里看到。
定义和简单推论
定义一个循环网络是说每条边有一个容量\(u(v,w)\)和整数费用\(c(v,w)\)，\(v\rightarrow w\)的流量\(f(v,w)\)/费用和\(w\rightarrow v\)的流量/费用是相反数。
伪流是可以不流量平衡的流，一个点的超额流\(e(v)\)是它所有出边流量之和，称超额流为正的点是溢出的，循环流是所有点超额流都为\(0\)的伪流。
循环流的费用是所有边流量乘费用，加起来除以\(2\)，这个除以\(2\)是因为每个流算了两遍。
定义一个环的费用是环上所有边的费用和，平均费用是费用除以长度。
给每个点定义势能(price function)\(p(u)\)。定义边\((u,v)\)的reduced cost(试译为 简化费用?)是\(c_p(u,v)=c(u,v)-p(u)+p(v)\)。容易知道使用\(c\)和\(c_p\)不影响最小费用循环流，所以以下如果没有特殊说明或者懂的都懂，说的费用都是简化费用，但是\(c\)是原费用，\(c_p\)是简化费用。
定理1 一个循环流是最优的(最小费用的)，当且仅当不存在残存的负环。
证明 废话。
当然最小费用循环流的增广指的是找到负环然后在上面转圈。
定理2 一个循环流是最优的，当且仅当存在一组势能\(p\)，使得对于任意边\(v,w\)，有
\[c_p(v,w)<0\Rightarrow f(v,w)=u(v,w)\]。
证明 充分性显然，因为不再有残存的负环，我们不可能再增广了。你说有没有可能走了正环?那在这个环上退流就是负的费用。正环和负环是对应的。
必要性也显然，因为最小费用了，那么没有残存的负环，我们按照Johnson取最短路来作为\(p\)就好了。好像有更快的方法，不过没大问题。
定义一个伪流是\(\epsilon\)最优的，当且仅当存在一组势能\(p\)，使得对于任意边\(v,w\)，有
\[c_p(v,w)<-\epsilon\Rightarrow f(v,w)=u(v,w)\]。
定理3 一个循环流是\(\frac{1}{n}\)最优的，那么它就是最优的。
证明 考虑任意一个环的费用一定\(>-1\)，而因为费用是整数，这个环的费用肯定\(\geq 0\)。
容易知道，任意一个循环流都是\(C\)最优的，所以如果我们每轮把\(\epsilon\)缩小一半，\(\log(nC)\)轮之后就会得到答案。
Refine
refine是cost scaling的核心。它接受一组\(\epsilon,f,p\)，其中\(f\)是\(\epsilon\)最优的，\(p\)给出了此时的势能，它将\(\epsilon\)除以\(2\)，计算一组\(\epsilon\)最优的\(f,p\)。
首先假设你会push-relabel，但是这里的push-relabel不太一样，所以你不会也行。
定义\(\mathrm{push}(v,w)\)说的是，对于一个溢出点\(v\)和负边\((v,w)\)，把它的超额流沿着\((v,w)\)尽可能多地推给点\(w\)。
定义\(\mathrm{relabel}(v)\)说的是，对于一个没有负出边的溢出点\(v\)，把它的势能尽可能少地抬高使得现在有至少一条负出边，这个负出边的费用应该是\(-\epsilon\)，也就是说把它的势能改成
\[\min_{f(v,w)<u(v,w)}p(w)+c(v,w)+\epsilon\]。
我们称一次push是饱和的(saturating)，当且仅当它把一条边充满了。分析时称relabel之后的势能函数是\(p^\prime\)。
引理1 一个溢出点要么可以push，要么可以relabel。
证明 废话。
引理2 push保持\(\epsilon\)最优，也就是说本来\(\epsilon\)最优的伪流不会变成不是\(\epsilon\)最优的，但是不是\(\epsilon\)最优的也可能变成\(\epsilon\)最优的。
证明 显然。
引理3 对\(v\)做一次relabel至少使得\(p(v)\)增加\(\epsilon\)，并且relabel保持\(\epsilon\)最优。
证明 第一部分显然。
第二部分，考虑只有\(v\)的邻边会改变费用，其中所有\((w,v)\)的费用上升了，它们不需要考虑，只有\((v,w)\)的费用下降了。
考虑一条没有满的\((v,w)\)，因为relabel是尽可能少地增加势能，有\(p^\prime(v)\leq p(w)+c(v,w)+\epsilon\)，所以我们知道\(c_{p^\prime}(v,w)\geq-\epsilon\)。
好了现在我们可以给出完整的refine了。我们首先把\(\epsilon\)砍一半，然后充满所有负边，用一个数据结构维护溢出点，进行push/relabel直到不再有溢出点。
现在我们的任务就是证明它的正确性，以及复杂度了。
定理4 refine是正确的，也就是说它确实会给出一组\(\epsilon\)最优的\(f,p\)，这里的\(\epsilon\)是砍一半之后的。
证明 你发现所有费用足够负的边一上来都被充满了，这样我们得到一个\(\epsilon\)最优的伪流，而push/relabel保持它的\(\epsilon\)最优，在push/relabel结束之后没有溢出点，所以我们得到了一个\(\epsilon\)最优的循环流。
定理5 不管你使用啥数据结构维护溢出点，每一轮refine，只有\(O(n^2)\)次relabel，\(O(nm)\)次饱和push，\(O(n^2m)\)次不饱和push。
证明 咕咕咕。
定理6(Wave implementation) 如果我们使用队列维护溢出点，一轮refine复杂度会变成\(O(n^3)\)，当然我们认为\(m=\Omega(n)\)。
证明 还是咕咕咕。
定理7 cost scaling是强多项式的，它在\(O(\min(m\log n,\log(nC)))\)轮后会得到答案。
证明 咕咕咕咕咕。
于是我们得到结论 : 如果值域不是 非 常 大，cost scaling的复杂度是\(O(n^3\log(nC))\)。这看起来比capacity scaling快不少。
如果使用动态树，可以得到更好的时间界，但是实际上跑的更慢，并且我们用double scaling也可以得到差不多的界。
Double Scaling
如果你不知道capacity scaling，可以去ouuan的blog学习一下。
如果你知道capacity scaling，那么double scaling就是在cost scaling的refine中采用capacity scaling的方法。它非常的牛逼，以至于可以做到\(O(nm\operatorname{poly}(\log v))\)。不使用动态树数据结构的话，可以做到\(O(nm\log U(1+\log(nC)/\log\log U))\)，使用的话则是\(O(nm\log(nC)\log\log U)\)。
在直接做之前，我们需要重要的一步，消除费用流问题的流量。这个听起来很离谱，但是继续往下看你就懂了。
定义一个transportation problem(试译 最小费用二分图流量平衡问题，以下简称 平衡问题)是，有一个二分图，每个点有一个需求，左部点的需求是负的，右部点是正的，需求总和是\(0\)，每条边有费用而没有容量上限，求一个流使得供需平衡并且费用最小，供需平衡指的是左部点流出去的等于它的需求(的绝对值)，右部点流进来的等于它的需求。
容易把一个最小循环流转化成平衡问题，也就是给每条边(不包括反向边)建一个虚点，所有的虚点构成二分图的左部，原图中的点构成二分图的右部。每条边的虚点连向它的两个端点，连向起点的费用是\(0\)，而连向终点的费用是这条边的费用。对于一条边的虚点，它的需求是负的容量；对于原图中的一个点，它的需求是出边的容量之和。一条边的虚点的一个单位需求，流向起点表示原图中不流这条边的这个单位，流向终点表示原图中流了这条边的这个单位，这样我们就可以在最小循环流和平衡问题的可行解之间转化而费用不变，于是平衡问题的最优解就是对应的最小循环流的最优解。
注意到直接用这个看起来没有任何帮助 : 总点数是\(n+m=O(m)\)，边数也是\(O(m)\)，于是即使用最快的二分图带权匹配也会有一个\(m^3\)这样的东西，就直接飞了。
用在平衡问题上的dinic看起来像是push-relabel，同时capacity scaling被称为excess scaling，因为容量变成了溢出的需求。我们从一个极大的\(\Delta=2^k\)开始，每次把\(\Delta\)减半，并且检查所有需求的溢出量超过\(\Delta\)的结点，对它们进行一轮push-relabel，每次push \(\Delta\)个单位。这个东西的复杂度是\(O(nm\log U)\)，因为它实在就是capacity scaling的dinic。