上下界网络流小结

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093889

正式请看：https://oi-wiki.org/graph/flow/bound/

无源汇上下界可行流

新建源汇 $S,T$ ，若 $a\to b$ 有 $[c,d]$ 。网络流中上界肯定满足。

我们变成：

1. $S\to b,c$

2. $a\to T,c$

3. $a\to b,c-d$

因为我们求的是可行流。若 $a$ 能流 $c$ 到 $b$ ，则 $b$ 必然可以流 $c$ 回 $a$ 。前两天边就是为了实现这个判断的过程。最后一条是上界的限制。

有源汇上下界可行流

发现源点和汇点为特殊点，因为他们流入流量不等于流出流量。

所以 $T\to S, [0,+\infty]$

然后跑无源汇上下界可行流

有源汇上下界最大流

在 有源汇上下界可行流 的残余网络中删掉附加变跑 $S\to T$ 最大流，最后加上可行流。

有源汇上下界最小流

同上，不过跑的是 $T\to S$ 的最大流。然后让可行流减去这个最小流。

感性理解。