主题

主题

 
   

上下界网络流

王队长给出了一种方法。似乎和以前的不同。


  • 无源汇可行流

在原来的办法中,我们是用一个deta[i]来记录连边。

具体方法是这样的:

(原链接:http://liaoy148.lofter.com/post/1da8a74e_d8d10a6

对于一条<u,v,l,r>的边,先连一条<u,v,r-l>的边,之后令D[u]+=l,D[v]-=l。

操作完之后,对于每一个点,如果D[u]>0(说明出去的下界流大于进来的下界流,那么我们人为补充一些流),从ss连一条边vol=abs(D[i])的边到i,否则从i连一条vol=abs(D[i])的边到tt。

判断是否可行的条件是:

s或者t连的边的所有容量,就是存在可行方案的最大流的大小。

我们跑完最大流之后,看最大流与容量之和是否相等,相等即存在,不相等即不存在。


这些天王队长提出了另外一个做法。不需要区分啥的。

对于一条<u,v,l,r>的边,同样连接一条<u,v,r-l>的边。

之后连接一条<ss,v,l>与<u,tt,l>的边(这些边被称之为辅助边)。

判断是否可行的条件是:

 跑SS->TT的最大流,如果所有辅助边满流,则有解。


这样做的原理是把下界流提出来,用ss与tt去满足。比方说如果v要被u输入至少x的流,就让ss输入给v。

这样做的好处不仅仅是不用分类讨论。


  • 有源汇可行流

方法是这样的:

视为还存在一条<t,s,0,none>的边。转换为无源汇网络流即可。

由于这条边下界为0,所以<ss,s,0>与<t,tt,0>是无意义的。只需要在网络流图中添加一条<t,s,none>的边。


这样做的原理是把s与t强行变为流量平衡。


  • 有源汇最小流

方法是这样的:

记我们新添加的<t,s,none>这条边的流量记为f,删除这条边。

残图上跑t到s的最大流,记为maxflow。

原图最小流为f-maxflow。


  • 有源汇最大流

方法是这样的:

记我们新添加的<t,s,none>这条边的流量记为f。

残图上跑s到t的最大流,即为maxflow。

原图最大流是f+maxflow。

 
 
评论