Question

运筹学作业.!!!!求下图s到t的最大流，并找出最小割，

Answer 1

算般存-定理

1 、匹配覆盖

2、 流割

流-割定理理解引自呆欧形象表达：粗管水流量比自水厂用水户工业区A 能达水流量考虑能水厂区少达水管流量等于拆掉少细水管水厂能给区A 供水些水管流量集合种说并严谨水管双向网络谈论信息流却双向

其实流-割难于构图必须掌握Dinic算

高效求流算——Dinci算：

Dinci算基于层图间效率优先流算

层：源点走终点短路度层图：每源点终点距离短并且记录条增广路径（找短路程记录条增广路径找短路径程自叉叉增广路径条数变）dfs遍历候必须按照层走

Dinic算思想减少增广数建立辅助网络LL与原网络G具相同节点数边容量所同L进行增广增广流值写原网络再建立前网络辅助网络反复达流

Dinic三步曲：

1、利用原网络构造层图顺便判断原网络增广路

2、利用构造层图求流若找增广路则算结束

3、更新原网络即增广程遇见边其边及逆边容量

重复述三步