上下界网络流就是在网络流的基础上,给了每条边一个上下界的限制,要求经过该边的流量必须在这个范围内。

上下界网络流有四种模型,下面会一一讲解建模以及感性理解。

建模

首先建一个源点 $S$ 和一个源点 $T$。

对于每条边 $(u,v,lower,upper)$,从 $u$ 向 $v$ 连一条容量为 $upper-lower$ 的边,然后将 $d_v$ 加上 $lower$,$d_u$ 减去 $lower$。

对于每个点 $u$,如果 $d_u>0$ 则从 $S$ 向 $u$ 连一条容量为 $d_u$ 的边,否则从 $u$ 向 $T$ 连一条容量为 $-d_u$ 的边。

然后跑 $S$ 到 $T$ 的最大流,每条边的实际流量等于新图中的流量加上它的流量下界。如果与 $S$ 相连的边没有满流说明无解。

理解

对于每条边,我们先强制给它通入 $lower$ 的流量,让它能够达到下界。那么这条边最多还能流 $upper-lower$ 的流量。

但是这是网络流,因此每个点要满足流量平衡,而我们强制通入一些流量后每个点是不满足流量平衡的。

因此我们新建一个源点和一个汇点来解决这个问题。如果 $d_u>0$,说明 $u$ 需要额外流入 $d_u$ 的流量,因此从 $S$ 向 $u$ 连容量为 $d_u$ 的边;否则说明 $u$ 需要额外流出 $-d_u$ 的流量,因此从 $u$ 向 $T$ 连容量为 $-d_u$ 的边。

然后跑最大流,然而我们一开始是强制给每条边的流量加了 $lower$ 的,所以每条边的实际容量要加上 $lower$。

如果与 $S$ 相连的边没有满流的话,说明流量没有补满,从而无法满足下界的限制,所以无解。

代码

LOJ

建模

设原图的源、汇点为 $s,t$。

从 $t$ 向 $s$ 连一条边权为 $+\infty$ 的边,然后问题变为无源汇有上下界可行流。

理解

有源汇有上下界可行流不能直接向上面那么做的原因是什么?是因为源点和汇点的流量不平衡。

因此我们从 $t$ 向 $s$ 连一条容量为 $+\infty$ 的边,这样子源点和汇点就也满足流量平衡了。

然后就变成无源汇有上下界可行流了。

一个比较有用的结论是$(t,s)$ 边的流量就等于可行流的总流量。

建模

首先按照有源汇有上下界可行流的方法建模,先求一组可行流。

然后在求过可行流后已经有了一些流量的图上求出从 $s$ 到 $t$ 的最大流(这里的 $s,t$ 是原图中的源、汇点),即为答案。

理解

第一次求出可行流后,我们得到的是一个满足上下界限制的流。

为了让它称为最大流,我们想要每条边 $upper-lower$ 的额外流量尽量流满。

因此我们再求出从 $s$ 到 $t$ 的最大流,就得到了最多的额外流量,而原来可行流的总流量在 $(t,s)$ 边中,所以最后得到的实际上就等于最大流。

代码

LOJ

建模

首先按照有源汇有上下界可行流的方法建模,但是不要连从 $t$ 到 $s$ 的那条边,然后跑一遍从 $S$ 到 $T$ 的最大流(这里的 $S,T$ 是自己加的源、汇点)。

现在再连上从 $t$ 到 $s$ 的容量为 $+\infty$ 的边,再求出从 $S$ 到 $T$ 的最大流,即为答案。

理解

因为 $(t,s)$ 边的流量等于可行流的流量,因此我们会要想办法最小化 $(t,s)$ 边的流量。

于是我们想到在求这个之前先跑一遍最大流,来消耗掉一些流量,这样子再求最大流时得到的就是最小流了?

代码

LOJ


版权属于:M_sea

本文链接:https://m-sea-blog.com/archives/bound-flow/

转载时须注明出处及本声明

最后修改:2020 年 02 月 02 日 04 : 22 PM