最大流题1.png
图中括号外的数字代表允许容量，括号内的数字代表了实际流量。
解法步骤：
（1）在已知可行流基础上，通过标号寻找增广链。
正向寻找非饱和弧，若无正向，寻找反向非0弧。
image.png
（2）修改增广链上的流量，非增广链的流量不变，得到新的可行流。（调整量取最小值）
上图中看到调整量 [6，2，2]中最小的是2。
（3）调整后，擦除原标记，重新搜寻增广链。
image.png
（4）重新搜寻增广链。
image.png
调整量[4，1，1，1]最小是1，所以调整后得到
image.png
（5）之后不断寻找后，直到无法标号，即不存在增广链，此可行流就为最大流，此处为14。
image.png
从s开始还能往下寻找非饱和的节点，归为和s一个集合。
看另一个例题：
image.png
寻找增广链，即不断寻找正向（流出）非饱和边，如果没有的话看是否有逆向（流进）非0边。
逆向边修改流量的时候减少之。
image.png
v1到v5这个逆向边最多减少3个单位流量。
修改后：
继续寻找增广链：
image.png
最大流 W = 5 + 4 + 2 = 11
最小割集 {(Vs, V1), (Vs, V2), (Vs, V6)}
网友评论