上下界网络流

上下界无源汇可行流

求每条边流量的一组可行解,满足每个点的入流量等于出流量。

新建超级源,超级汇,把([u,v,high,low])的限制改为([u,v,high-low],[s,v,low],[u,t,low]),然后跑最大流。判断一下下界之和是否等于最大流即可。

上下界无源汇费用流

在上一题建的图中加权即可,新建的边不用,跑完判断有解后再计入答案

上下界有源汇最大流

源点(s),汇点(t)。超级源(ss),超级汇(tt)。首先判断是否存在可行流,加一条([t,s,inf])转成无源汇有上下界的可行流问题。

可以时,再从(s)(t)跑一个最大流即为答案。

简要证明:

之前超级源汇是跑满了,再跑不会经过超级源汇。

由于连了([t,s,inf]),可行流的流量已经在([t,s,inf])边中,跑最大流的时候,([t,s,inf])反向边就有可行流的流量,就不用加了。

上下界有源汇费用流

直接加上费用即可

上下界有源汇最小流

先不加([t,s,inf]),跑超级源到汇的最大流,再加上([t,s,inf]),再求最大流,此时([t,s])的流量就是答案。

简要证明:

(好好利用循环流)

第一遍并无([t,s,inf]),所以([s,t])的流量已尽力流向其它边 。

加上([t,s,inf])后,流过这条边是流不到其他边的流量,尽可能减少([t,s])流量,减小答案。

原文地址:https://www.cnblogs.com/aurora2004/p/13755140.html