最大流在信息学竞赛中应用的一个模型--江涛

NOI2006年冬令营讲座

图7.10

改造：由于可行流的源S流出与汇T流出应该是相等的，加条边(T,S)，容量+∞。割开所有必要弧，加两个附加源Y和汇X： 13 2 1 1 1 2 4 1 1 1 1 1 3 5

图7.11

X Y至此：问题成功转化为求Y到X的普通最大流问题。我们称这个改造后的网络模型为附加图络3。

NOI2006年冬令营讲座

回顾本节我们要解决的问题：

? 问题7.1：怎样求满足下界而又不超过上界的一个流f1？ ? 问题7.2：怎样增大流f1，而又同时不破坏下界？

当求出附加网络3的最大流为1+1+1+1+1=5时，我们再反过来做：把“进X”和“出Y”的对应边连上，则找到一个有上下界容量限制和无源汇可行流。再把弧(T,S)拿走，则问题7.1解决。

图7.12

1 1/1 2 1/+∞ 1/3 3 1/1 1/1 4 1/1 1/1 5 注意：原问题可行流存在无解情况，即附加网络3的最大流不能把源(或汇)相连的弧饱和。不同于普通最大流：因下界为0时，一定有解。

在得到一个可行流f1之后，现在我们再来看看问题7.2。

NOI2006年冬令营讲座

再去掉边(T,S)----上图即为弧(5,1)，还原成有源汇最大流的原问题。

如果要求这时的最大流，则可在这个基础上，找增广路径来增大流，最终求得一个符合要求的最大流方案。

但是要注意的是，对必要弧，我们不能退流，因此相应的残留网络对必要弧要单独处理，或直接暂时拿走，再做附加网络2，如果对上例处理，则：

图7.13

1/1 1 2 3 5 4

图7.14

1 2 0 1 4 3 5 当然，本例不可能再增大流了，例子仅对解决问题7.2的

NOI2006年冬令营讲座

图示说明。

另外，这种情况下的增广路径改进，不会影响必要弧---即：不破坏下界。