原来整理的好像有点问题重新写了一下qwq
有上下界的网络流就是每条边都有一个$l$和$r$，然后每条边的流量$flow$必须满足$l\le flow\le r$
一般分$4$种情况
无源汇可行流
-
一个
烂大街的错误
我会做这个！把每条边的容量设成$r-l$，然后求最大流，答案加上最大的$l$就完事了快夸我快夸我
其实仔细想想就有问题，这样做不一定满足流量平衡
-
正确做法
现在问题是如何满足容量平衡
假设现在不知道从哪来的一股流量$f$把点$i$补到流量平衡了，即有$\sum_{(a,i)\in E}l_{(a,i)}+f_{(a,i)}=\sum_{(i,b)\in E}l_{(i,b)}+f_{(i,b)}$
发现可以移项，$\sum_{(a,i)\in E}l_{(a,i)}-\sum_{(i,b)\in E}l_{(i,b)}=\sum_{(i,b)\in E}f_{(i,b)}-\sum_{(a,i)\in E}f_{(a,i)}$
式子左边的值（定为$v$）可以维护
- 如果$v> 0$，说明从$i$点流入的$f$大于从$i$点流出的$f$，网络流中只有源点和汇点不用满足流量平衡，所以新建源点$S’$，建边$(S’,i,v)$
- 如果$v<0$，说明从$i$点流出的$f$大于从$i$点流入的$f$，跟上面同理，新建汇点$T’$，建边$(i,T’,-v)$
这样跑$S’$到$T’$的最大流，如果每条从$S’$和每条连向$T’$的边都满流了说明有解（都流量平衡了）
有源汇可行流
因为源点和汇点不满足流量平衡，所以不能用无源汇的方法直接做……
那么把源点汇点改成流量平衡就好了
源点只会发出流量，汇点只会接受流量，这两个点的流入流出是相等的
所以只用建立边$(T,S,inf)$就能满足流量平衡了，总流量就是最后$(T,S)$的反向边流量
有源汇最大流
我不仅要有上下界，还要有源汇！
我不仅要有源汇，还要求最大！
当然要跑一遍可行流来看是否有解
如果$S’$发出的边和连向$T’$的边都流满了，说明这些点都达到了流量平衡，却不一定是最大的，即某些点可以增加流量的情况下依然满足流量平衡
发现求一遍可行流的残余网络相当于每个点都已经满足流量平衡的情况，因为这时候为了调节流量而建的$f$都已经满流，不能再继续发挥作用，这时候跑个$(T,S)$的最大流的答案加上刚才求一遍可行流的答案就是所求
这里残余网络的$(T,S)$如果不删，答案就是这时跑个最大流的答案，因为可行流的答案都存在$(S,T)$里，跑最大流会把$(S,T)$里的流量推到$T$
当然你甚至可以二分最大流$mid$，然后跑可行流判断，只要把$(T,S)$的容量定为$mid$即可，复杂度多个$log$不建议使用
有源汇最小流
我不仅要有上下界，还要有源汇！
我不仅要有源汇，还要求最小！
当然要跑一遍可行流来看是否有解
因为反向边流量增加相当于正向边流量减少，所以求最小流相当于求减少的最大流（？）
还是残余网络，跟最大流一个道理，求一遍从$T$到$S$的最大流相当于满足流量平衡的条件下尽量减少流量，刚才求一遍可行流的答案减去这时候跑个$(T,S)$的最大流的答案就是所求
注意这里要是不删去$(T,S)$边的话答案就是$inf$减去跑$T$到$S$的最大流
当然二分也是可以的……
就这样吧
