前置芝士
首先要比较清楚地了解网络最大流的原理以及\(dinic\)算法求最大流是过程
大力推荐博客liu_runda nb
无源汇上下界可行流
又称作循环流，这个网络流是没有源点和汇点的，只有流量在上面不停地循环
这个是其他上下界网络流的基础
\(n\)个点，\(m\)条边，每条边\(e\)有一个流量下界\(low\)和流量上界\(up\)，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。
两个限制一般会把自己搞掉，我们一个一个考虑，先考虑下界
只要我们先给每条弧都加一个\(low\)的流量下界这个限制就没了对吧，但是现在这个图很可能不满足流量平衡，我们姑且称当前图上的流量为初始流
我们应该在这张图上添加一个附加流，使得这个附加流加上初始流满足流量平衡
显然我们还要考虑上界，每条弧的附加流上限是\(up-low\)，所以我们建边的时候可以直接把容量设为\(up-low\)，把\(low\)提出来
考虑现在对于图中某个点\(i\),假设她现在的 总流入量-总流出量为\(c_i\)
那么如果这个\(c_i\)大于\(0\)，说明这个点她流入的流量有点多，应该流出一些（？
如果这个\(c_i\)小于\(0\)，说明她流出的太多了，应该注♂入♂灵♂魂♂
那这些多出来的和应该补充进入的流量怎么办呢？
我们可以设置虚拟源点和汇点
虚拟源点向每个\(c_i>0\)的点连边，容量为\(c_i\)
每个\(c_i<0\)的点向虚拟汇点连边，容量为\(-c_i\)
有人会疑惑为什么流入更多的还要流入，流出更多的还要流出吗？？？
因为我们并不是直接通过设置虚拟源点和汇点实现流量平衡的
虚拟源点和汇点的作用是：把刚开始不平衡的局面构造出来，然后通过\(dinic\)算法和原有的边实现流量平衡
如某个点\(x\)，它的\(c_x>0\)，那么我就从虚拟源点给他\(c_x\)的流，然后让这些流在原本的那些边上流动，直到流到某个\(c_y<0\)的点，通过这个\(y\)点流出
然后留在原有边上的流量是我们要求的附加流
如果我们能找到一个附加流加上初始流后流量守恒，那么直接与虚拟源点和虚拟汇点相连的边应该都满流
由于\(\sum\limits_{i\in V}[c_i>0]c_i=-\sum\limits_{i\in V}[c_i<0]c_i\)
所以如果能找到符合要求的附加流，那么在新图中的最大流应该等于\(\sum\limits_{i\in V}[c_i>0]c_i\)
求出最大流后怎么找到每条边的流量呢？
由于我们已经跑过\(dinic\)算法了，所以每条弧的反向弧中的流量就是这条弧所对应的附加流
有源汇上下界可行流
\(n\)个点，\(m\)条边，每条边\(e\)有一个流量下界\(low\)和流量上界\(up\)，给定源点\(S\)与汇点\(T\)，求源点到汇点的可行流。
这个东西就有点问题，因为\(S\)和\(T\)流量不守恒，刚刚我们处理的情况是所有节点流量守恒的情况
当然我们可以手动令它流量守恒，比如：由\(T\)向\(S\)连一条下界为\(0\)，上界为\(inf\)的边，就可以实现所有点流量守恒
然后重复刚才的过程，求一个循环流
然后把刚才加的那条边拆掉，我们就得到了一个有源汇上下界可行流
考虑这个有源汇上下界可行流的流量是多少？由于所有的流都会流入汇点，所以我们只要看最后\(T\)到\(S\)的反向弧中有多少流量
有源汇上下界最大流
\(n\)个点，\(m\)条边，每条边\(e\)有一个流量下界\(low\)和流量上界\(up\)，给定源点\(S\)与汇点\(T\)，求源点到汇点的最大流。
利用刚才的方法，我们已经求得了一个有源汇上下界可行流，那我们怎么得到有源汇上下界最大流？
由于目前我们的网络流中的流量已经平衡，所以我们只要在残量网络上再跑一个最大流即可
最终的最大流=有源汇上下界可行流+残量网络上最大流
考虑为什么不会超出上下界：
下界：我们在建图的时候下界并没有出现在原图中，下界是额外计算的，一定大于下界
上界：由于建边的时候流量为\(up-low\)，所以不会超过上界
其实实际操作起来很方便：只要先用虚拟源汇跑一遍\(dinic\)，然后不删除\(T\)到\(S\)的边，再用原本的源汇跑一遍\(dinic\)，得到的结果就是答案
为什么这样做是对的？
因为考虑第一次用虚拟源汇跑完\(dinic\)后，原图中留下的本就是残量网络
且原本的可行流应该保存在\(T\)到\(S\)的反向边中，然而我们这次跑的是\(S\)到\(T\)的最大流，这些流量刚好会被加上~
有源汇上下界最小流
\(n\)个点，\(m\)条边，每条边\(e\)有一个流量下界\(low\)和流量上界\(up\)，给定源点\(S\)与汇点\(T\)，求源点到汇点的最小流。
思路完全类似，先求出有源汇上下界可行流
考虑在可行流基础上减去一个守恒的流量
需要深入理解\(dinic\)的反向边，我们如果找到一条从\(T\)到\(S\)的增广路，就说明去掉这条增广路上的流量，网络流仍然守恒
所以我们可以直接从\(T\)向\(S\)跑一波最大流，用可行流减去这次最大流的值，即为有源汇上下界最小流
注意这次不能留下那条\(T\)到\(S\)的\(inf\)边了\(qwq\)
上下界分析相同