Posted in: 算法讲稿

上下界网络流 – 学习笔记

标定

考虑每条边的流量范围:$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$。

代码:

Back to Top