上下界网络流学习笔记

无源汇上下界可行流

这个的思想是上下界网络流的基础，我们先钦定每条边流下界的流量，然后再调整。

假设有边 ((u,v,lower,upper))，钦点流量下界之后有一部分流量是可流可不流的，于是我们在原图中连边 ((u,v,upper-lower))。

同时我们统计每个点流入的流量和流出的流量的差，记为 (delta[u])，然后建立超级源汇 (ss,tt)

如果 (delta[u] > 0)，我们连边 ((ss,u,delta[u]))，如果 (dealta[u] < 0)，我们连边 ((u,tt,-delta[u]))

那么如果 (ss) 到 (tt) 可以跑满流那么就是有解的，这说明每个点多余的流量都可以绕整个网络然后去补充那些缺少流量的点，从而达到流量平衡。每个边的流量显然也是满足限制的。

然后每个边的下界加上它们的流量就是方案。

同上，直接连边 ((t,s,inf))，就变成了一个无源汇的问题。

先求出一个可行流，然后在删除所有新加边的残量网络上跑 (s) 到 (t) 的最大流，用尽自由流量。

这样可行流加上我们第二次跑的最大流就是答案。由于新加入的边，我们同样会考虑 (s) 和 (t) 这两个点的流量平衡，所以我们不需要额外的去考虑每条边的下界。

在程序实现当中有一个 (trick)，我们保留新加入的边。这样直接跑 (s) 到 (t) 就是答案。

因为加边 ((t,s)) 同样会加入反向边，这样第一次跑 (ss) 到 (tt) 的最大流，(s) 到 (t) 的可行流量就会变成反向边的容量。这样同样可以方便地处理图不连通的情况。（比如图分成两部分，上面有 (s) 和 (t)，然后另一个部分的可行流和我们的答案没有任何关系。）

[#116. 有源汇有上下界最大流](#116. 有源汇有上下界最大流)

同上，我们求出 (s) 到 (t) 的可行流量（注意取可行流量要看边 ((t,s))），然后我们删去新加的边，从 (t) 到 (s) 跑最大流，尽可能的流去自由流量，两次相减就可以得到最小流。

[#117. 有源汇有上下界最小流](#117. 有源汇有上下界最小流)