[学习笔记]有上下界的网络流
2021/11/25 6:12:28
本文主要是介绍[学习笔记]有上下界的网络流,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
对于有上下界的网络流问题,涉及判是否有解及求解最大/小流,费用流.
基本建图
建立超级源\(S\),超级汇\(T\).
对于边\((u,v)\)=\([l,u]\),将其拆成三条边:
- \((S,v)=l\);
- \((u,v)=u-l\);
- \((u,T)=l.\)
因为对于边\((u,v)=[l,u]\),
\(u\)至少流出\(l\)的流量,\(v\)至少流入\(l\)的流量,所以建边\((S,v)=l,(u,T)=l\);
而\(u->v\)有\(u-l\)的流量是自由流,所以建边\((u,v)=u-l\).
显然\(S->u,u->T\)有可能有多条边,合并这些边,节省空间.
无源汇
可行流
求\(S->T\)的最大流,从\(S\)出发的边全部满流则可行,因为说明所有边的下界均已满足.每条边的实际流为自由流+流量下界.
有源汇
可行流
加一条边\((t,s)=+\infty\).转成无源汇.
求\(S->T\)的最大流,从\(S\)出发的边全部满流则可行.
最大流
求出可行流后,在残量网络上求\(s->t\)的最大流.
理由:
\(s->t\)跑的是\(S->T\)的反向边,这时下界的流量已经在反向边中了,\((t,s)=+\infty,S,T\)不会影响到最大流,所以是合法的答案.
最小流
先不加\((t,s)=+\infty\)这条边,这时跑\(S->T\)的最大流可求出\(t->s\)的最大流,也就是在合法的情况下最多能减去多少.
然后再加\((t,s)=+\infty\)这条边,此时残量网络\(S->T\)的最大流即为答案.
2017-03-14 11:20:47
这篇关于[学习笔记]有上下界的网络流的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南