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

NOI2006年冬令营讲座

类似地，我们设法运用流分离的思想，找一个等价的附加网络3，使问题7.1和问题7.2得到方便而统一地解决。

(一)观察一条路径情况

图7.4

S 2,6

1 3,4 2 3,7 T 如同例7.1直接把容量下界减掉怎样？

图7.5

S 4

1 1 2 4 T 显然，如果图7.5中的流想通过加上下界来对应地得到图7.4中的解是不可能的。因此，这里流的分离不能用简单减掉的方法，而应该把一个弧分离成两个弧。即加一个容量等于下界的必要弧，使可行流分离在这两个弧上。如下图：

S 4 1 2

1 2 3

4 T 3

NOI2006年冬令营讲座

图7.6

一个无源汇的可行流的方案一定是必要弧是满的。因此现在我们先要找一个把必要弧充满的可行流(当然也要满足上界限制)。

现在我们的目光焦点是必要弧，把他们集中起来：

4 1 4 2

图7.7

S 1 T 2 3 3 由于必要弧都是要饱和的，显然与下面图是等价的。

S 4 1 1 2 3 3 4 T 2 2 3 3 X Y NOI2006年冬令营讲座

图7.8

NOI2006年冬令营讲座

进一步，加弧(T,S)，容量不限，成无源汇可行流问题。再去除X,Y之间的连线，使Y、X分别成为新的源和汇。

图7.9

2 4 +∞ 1 1 3 3 2 3 3 2 4 S T X Y 如果Y到X的最大流能为2+3+3，则显然有：

? 必要弧为满 ? 满足容量上界限制 ? 保持流平衡 (二)网络整体情况

再来看看例5.1，先分离必要弧： 3 0 0

1 1 2 1 0 1 0 4 1 3 1 5