分类： 算法讲稿
上下界网络流 – 学习笔记
标定
考虑每条边的流量范围：$b(u, v) \leq f(u, v) \leq c(u, v)$。
无源汇上下界可行流
首先我们给这条边标入最大限制 $c(u, v) - b(u, v)$，并默认认为该边已经流入了 $b(u, v)$ 的流量，然后我们可以给每个点设置一个 $M_i$ 来进行流量搜集。
如果：
- $M_i = 0$，那没啥问题。
- $M_i > 0$，说明下界要求流入的流量更多，所以我们从附加源点 $S$ 连到此点。
- $M_i < 0$，同理，说明下界要求流出的流量更多，所以我们专门开辟一个通道为此点流出至附加汇点 $T$。
代码：