上下限最大流

一、有上下限的最大流:首先,每条边的下限是必须要满足的。增加附加源点S和附加汇点T,原来的源点和汇点为s和t。对于原图G(s,t,low[u][v],high[u][v])构建相应的新图D(S,T,E),E包括,<t,s,INF>,<S,i,in[i]>,<i,T,out[i]>,<u,v,high[u][v]-low[u][v]>。其中,in[i]表示进入i的边的下限之和,out[i]表示离开i的边的下限之和。设sum为所有点的in值之和。然后求S到T的最大流A,若A不等于sum则不存在满足题意的可行流。否则删去边<t,s,INF>,接着求s到t的最大流B,则最大流为A+B,此时每条边的实际流量为此时每条边的流量加上每条边的下限。

二、有上下限的最小流,有两种方法:

(1)构建的新图D和上面的D是一样的。也是先求S到T的最大流,此时记录<t,s>边的流量A,然后删掉边<t,s>,接着求t到s的最大流B,则答案为A-B。此时A-B有可能为0,原因是这个图本来最小流为0,由于有环的存在这个图可以自给自足,此时增加S到s的边<S,s,B-A>,再跑S到t(此时是原来图的汇点t)的最大流。这样,每条边的流量加上下限就是每条边的实际流量。

(2)二分t到s的上限,x=in[i]-out[i],x>=0,连边<S,i,x>,sum+=x,否则<i,T,-x>。求S到T的最大流,大于等于sum则可行。

原文地址:https://www.cnblogs.com/jianglangcaijin/p/6036340.html