学一次忘一次,搞笑。
规定 \(s\) 和 \(t\) 为原图的源汇点,\(S\) 和 \(T\) 为新建的虚拟源汇点。
无源汇上下界可行流
考虑先把每条边的下界流满,然后网络的边权改为 \(r-l\)。但这样每个点的流量平衡不能保证,我们建源点 \(S\) 和汇点 \(T\),如果一个点的入量大于出量,就从 \(S\) 到它连一条边,边权为差值,入量小于出量就从它到 \(T\) 连一条边。这样如果把 \(S\) 和 \(T\) 撤走流量就平衡了。跑一次最大流即可。
有源汇上下界可行流
从 \(t\) 到 \(s\) 连一条边,流量为 \(+\infty\) ,转化为无源汇上下界可行流。
有源汇上下界最大流
跑一次有源汇上下界可行流,然后撤去虚拟源汇点和 \(\infty\) 的边,在残量网络上再跑一次最大流即可。
有源汇上下界最小流
- 用 \(S\) 到 \(T\) 的可行流减去残量网络上 \(T\) 到 \(S\) 的最大流。
- 二分答案 \(ans\),从 \(t\) 到 \(s\) 的边流量改为 \(ans\),
判定是否存在可行流。