首页 > 代码库 > Note:上下界网络流的理解

Note:上下界网络流的理解

无源汇可行流

弧流量限制条件 b(u,v)<=f(u,v)<=c(u,v),(u,v)∈E

不妨设f(u,v)=b(u,v)+f1(u,v),

Σ( b(u,v)+f1(u,v) ) = Σ( b(v,w)+f1(v,w) )

Σ b(u,v) - Σ b(v,w) = Σ f1(v,w) - Σf1(u,v)

 

若存在可行流,0<=f1(u,v)<=c(u,v)-b(u,v),且保证下界流流满。

 

可以加超级源S,超级汇T。

假定某条边(u,v)的流量限制是[b,c],等价于S→v流量b,u→T流量b,u→v流量c-b。

我们可以从S到T做一遍最大流,若满载,则下界流都能流满,即存在可行流。

 


 

有源汇可行流

有源汇s→t的上下界可行流,从t到s连一条流量INF的边,再按照无源汇一样做。

 


 

有源汇最大流

 

从t到s连一条流量INF的边,加超级源S和超级汇T,从S到T做一遍最大流。

若满载,则存在可行流。已经保证下界流流满。

再从s到t做一遍最大流,得到的是所求的答案。

 


 

有源汇最小流

从t到s连一条流量INF的边,加超级源S和超级汇T,从S到T做一遍最大流。

若满载,则存在可行流。已经保证下界流流满。

再从t到s做一遍最大流,得到的是所求的最小流。(可能打脸)