上下界流问题总结

无源无汇可行流

以前写的最大流默认的下界为0,而这里的下界却不为0,所以我们要进行再构造让每条边的下界为0,这样做是为了方便处理。对于每根管子有一个上界容量up和一个下界容量low,我们让这根管子的容量下界变为0,上界为up-low。可是这样做了的话流量就不守恒了,为了再次满足流量守恒,即每个节点"入流=出流”,我们增设一个超级源点ss和一个超级终点tt。我们开设一个数组du[]来记录每个节点的流量情况。

du[i]=in[i](i节点所有入流下界之和)-out[i](i节点所有出流下界之和)。

当du[i]大于0的时候,ss到i连一条流量为du[i]的边。

当du[i]小于0的时候,i到tt连一条流量为-du[i]的边。

最后对(ss,tt)求一次最大流即可,当所有附加边全部满流时(即maxflow==所有du[]>0之和),有可行解。

sgu-194-Reactor Cooling(无源汇有上下界最大流)

处理有源汇有上下界最大流问题是:
1.构造附加网络
2.对ss、tt求最大流(ss、tt满流则有解)
3.若有解,对s、t求最大流

而有源汇有上下界最小流问题则是:
1.构造附加网络(不添加[t,s]边)
2.对ss、tt求最大流
3.添加[t,s]边
4.对ss、tt求最大流
5.若ss、tt满流,则[t,s]的流量就是最小流

原文地址:https://www.cnblogs.com/arbitrary/p/3119556.html