首页 > 代码库 > 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做一遍最大流,得到的是所求的最小流。(可能打脸)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。