【算法笔记】上下界网络流问题

无源汇可行流

1. 问题分析：
   因为只比传统网络流多了下界，所以考虑单独考虑下界的流量

2. 解决方案：
   于是原来的边拆为上界为min的边并强行满流，和上界为max - min的边。
   但这样可能会出现流量不平衡的状况，及一个点流入的流量不等于流出量。
   于是单独增加源汇点，构造一个完全等价的网络流问题
   
   至此我们已经将问题转化为传统网络流问题，直接求解即可。
   如何判断是否有可行流的根据也显而易见了：\( Max\_Flow = = \sum {Min\_Flo{w_i}}\)

有源汇可行流

1. 问题分析：
   有源汇意味着有一对点的流量不守恒，就是这一对点使其于无源汇可行流问题有了差别
   于是我们考虑去掉这个不同点，将其转化为无源汇可行流

2. 解决方案
   我们注意到，将源汇点连上一条容量INF的边之后，所有的点流量都守恒了
   换一句话来说我们将其转化为了无源汇可行流问题，使用上文所述方法求解即可

有源汇最大流/最小流

1. 通解通法：
   观察可行流的解决方案，不难发现我们控制我们人为增加的那条边的容量即可控制最大流的容量
   所以我们可以二分最大流/最小流，之后进行可行流判断，再之后根据结果进行调整即可

2. 最小流的高效算法：
   先不连t-s的那条容量为INF的边，先跑一次附加源汇的最大流
   连t-s的那条边，在残量网络上继续跑附加源汇最大流
   此时t-s那条边的流量是最小的，使用上文所述方法判断其是否为可行流即可

3. 最大流的高效算法
   连t-s的那条容量为INF的边，跑一次附加源汇最大流
   连t-s的那条边，在残量网络上继续跑s-t的最大流
   此时t-s那条边的流量是最小的，使用上文所述方法判断其是否为可行流即可