无/有源汇 上下界 可行/最大/最小流

无源汇

上下界可行流

每条边都存在下界 $b(u,v),c(u,v)$ 分别表示这条边的流量至少、至多为多少。

1. 我们先直接假设每条边已经流了 $b(u,v)$ 的流量，设为初始流量
2. 然后构造新图 $H$，其中的每一条边 $e_H(u,v)$ 满足其容量为 $c(u,v)-b(u,v)$
3. 然后对 $H$ 中的节点 $i$ 进行调整，假设 $H$ 中两个额外的点 $S,T$ 分别作为 $H$ 中的源汇点
   1. 如果初始流量中 $i$ 的收支平衡，则不用添加边
   2. 如果 $i$ 的入流多于出流，差值为 $d$，则 $S$ 向 $i$ 连边，容量为 $d$
   3. 如果 $i$ 的出流多于入流，差值为 $d$，则 $i$ 向 $T$ 连边，容量为 $d$
4. 然后以 $S$ 为源点，$T$ 为汇点跑最大流。
5. 如果 $S$ 出发的边都满流，则存在可行流；否则不存在

有源汇

上下界可行流

设源点为 $S$，汇点为 $T$，则我们连 $T\to S$ 的边，其下界为 $0$，上界为 $\infin$。于是问题转化为无源汇上下界可行流。

此时若有解，$S\to T$ 的可行流的流量就等于 $T\to S$ 的附加边的流量。

上下界最大流

上下界最小流