网络流进阶。主要是有上下界的各种网络流或费用流以及几个消负环的方法。
在看这个 Blog 之前你最好已经熟练掌握了 Dinic 网络流和 EK 费用流。
1. 无源汇有上下界的循环流
这是最简单的一种有上下界的网络流，也是所有有上下界的网络流的基础。
其所求大意如下：对于一张网络流的图，每条边有一个流量限制 \([l,r]\)，现在需要给每条边分配一个流量，使得每个点的流量平衡（即流入等于流出），且每条边的流量满足限制。
考虑先把每条边的流量设为其下界，设置完之后我们得到了一个初始流，这个流的流量都满足边的限制，但是不一定满足流量平衡。
考虑构造一个附加流，使得初始流加上附加流在满足边的限制的情况下满足流量平衡。
因为这个附加流仍需要满足边的限制，所以原来的一条边 \((u,v,l,r)\)，可以看成是一条 \(u\) 连向 \(v\) 的流量为 \(r-l\) 的边，这样在附加流中这条边的流量就只能是 \([0,r-l]\)，一定会满足边的限制。
然后就只需要考虑流量平衡。对于一个点 \(x\)，如果其流入大于流出，那么它就仍然需要流出一些流量。考虑新增一个虚拟起点 \(S'\)，连一条 \(S'\) 到 \(x\) 流量为流入和流出的差值的边。这条边每有 \(1\) 个流量，就代表在附加流中 \(x\) 点的流出增加了 \(1\)。类似的，如果点 \(x\) 的流出大于流入，那么它就仍然需要流入一些流量，就新增一个虚拟终点 \(T'\)，连条 \(x\) 到 \(T'\) 流量为流出和流入的差值的边。这条边每有 \(1\) 流量，就代表在附加流中 \(x\) 点的流入增加了 \(1\)。
最后对新图 \(S'-T'\) 跑一遍最大流，由前文的构造附加流的过程可知，可以使得其流量平衡当且仅当该图的最大流使得所有 \(S'\) 连出的边都满流（\(S'\) 连出的边都满流等价于 \(T'\) 连入的边都满流），否则的话无解。
最后每条边的流量就是下界加上附加流中该边的流量。
2. 有源汇有上下界的可行流
有源汇和无源汇的最大的区别就是源点 \(S\) 和汇点 \(T\) 的流量不平衡。
考虑连一条 \(T\) 连向 \(S\) 流量下界为 \(0\) 上界为 \(+\infty\) 的边，这样 \(S\) 的流出和 \(T\) 的流入就都可以靠这条边来弥补，使得其流量平衡。
这时候就只需要求循环流了，即 1.。
不难发现，\(T\rightarrow S\) 的流只可能走我们新加的边，所以附加流的总流量就是新加边的流量。但是这并不意味着新加边的流量等于 \(S'\rightarrow T'\) 的最大流，因为原图中可能有环。
而可行流的流量就是 \(S\) 的流出量（也就是 \(T\) 的流入量），也等于新加边的流量。故可行流的流量等于附加流的流量。
3. 有源汇有上下界的最大流
和 2. 类似的，我们可以先求出一个可行流。
此时对原图的残量网络再跑一次 \(S-T\) 的最大流即可。
需要注意的是，这里跑最大流的是原图的 \(S-T\)，而不是构造出来求附加流的虚拟节点 \(S'-T'\)。
如果你在跑 \(S-T\) 最大流的时候，去掉了前面所加的 \(T\) 到 \(S\) 的边，那么最大流就是残量网络上求出的最大流加上附加流的流量。否则，根据网络流的性质，此时可以通过所加的 \(T\) 到 \(S\) 的边的反向边，直接从 \(S\) 到 \(T\) 流附加流的流量，所以最大流就是残量网络上求出的最大流流量 。
4. 有源汇有上下界的最小流
和 2. 类似的，我们可以先求出一个可行流。
然后考虑从 \(T\) 向 \(S\) 退流，这样就可以使得流量尽可能小。
即在残量网络上跑一遍 \(T-S\) 的最大流。用附加流流量减去这个最大流的流量即最小流。
需要注意的是，这里跑最大流的是原图的 \(T-S\)，而不是构造出来求附加流的虚拟节点 \(T'-S'\)。
此时前面所加的 \(T\) 到 \(S\) 的边必须要去掉，不然会通过这条边退 \(+\infty\) 的流导致求不到答案。
5. 有源汇有上下界的最小费用可行流/最大流/最小流
为了方便，暂时不考虑负环，后面会提到两个消负环的算法。
最大费用和最小费用等价，所以暂且不考虑最大费用。
其实本质上就是在 2.3.4. 的基础上，加上一个最小费用。
即在一开始每条边强行流 \(l\) 的流量的时候，把总费用加上 \(l\times cost\)。
所有辅助边的费用都设为 \(0\)。
在求附加流的时候是跑的最小费用最大流。最大流不满流仍然无解。
最后在残量网络上面跑的时候，如果是 \(S-T\)，跑的是最小费用最大流，如果是 \(T-S\)，跑的是最大费用最大流（正着流费用最小就是退的流费用最大）。
6. 有上下界的另一种连边方法
为了省事，可以把边 \((u,v,l,r,c)\) 拆成三条边。一条 \(u\) 到 \(v\) 流量为 \(r-l\) 费用为 \(c\)，一条虚拟起点 \(S'\) 到 \(v\) 流量为 \(l\) 费用为 \(0\)，一条 \(u\) 到虚拟终点 \(T'\) 流量为 \(l\) 费用为 \(0\)。并把总费用加上 \(l\times c\)。
不难发现这种连边方法和 1. 的连边方法本质相同。只是把之前所考虑的一个点总流入和总流出的差分解成了若干个部分，或者说可以看成是之前直接把所有形如 \(S'\rightarrow x \rightarrow T'\) 的流全部流完了。
7. 消负环算法
对于一条负权边 \((u,v,l,r,c)\)，我们可以先强行把这条负权边流满，并获得 \(r\times c\) 的总费用，然后这条边就变成了从 \(v\) 连向 \(u\) 的流量为 \(r-l\) 的费用为 \(-c\) 的边。这样强制流之后显然不一定满足流量平衡，所以需要用上述的附加流的方法使其流量平衡。
因为在整个图中一开始没有出现负环，所以在整个过程中也不会产生负环（可能比较糊……暂时还没有证明，或许显然？）。
另外还有一种很神的消负环算法，可见这位神仙的博客。