上下界网络流

发布时间 2023-10-06 21:22:01作者: Aria_Math

学一次忘一次,搞笑。
规定 \(s\)\(t\) 为原图的源汇点,\(S\)\(T\) 为新建的虚拟源汇点。


无源汇上下界可行流

考虑先把每条边的下界流满,然后网络的边权改为 \(r-l\)。但这样每个点的流量平衡不能保证,我们建源点 \(S\) 和汇点 \(T\),如果一个点的入量大于出量,就从 \(S\) 到它连一条边,边权为差值,入量小于出量就从它到 \(T\) 连一条边。这样如果把 \(S\)\(T\) 撤走流量就平衡了。跑一次最大流即可。


有源汇上下界可行流

\(t\)\(s\) 连一条边,流量为 \(+\infty\) ,转化为无源汇上下界可行流。


有源汇上下界最大流

跑一次有源汇上下界可行流,然后撤去虚拟源汇点和 \(\infty\) 的边,在残量网络上再跑一次最大流即可。


有源汇上下界最小流

  1. \(S\)\(T\) 的可行流减去残量网络上 \(T\)\(S\) 的最大流。
  2. 二分答案 \(ans\),从 \(t\)\(s\) 的边流量改为 \(ans\)
    判定是否存在可行流。

参考资料:

Pecco

Alex-Wei