AC. 梦想

frank_c1

有上下界网络流

发布于2016年03月21日 | 暂无评论 | 1,509阅读 | 有上下界网络流

有上下界网络流大致可以分为下面几类问题。

在下列叙述中,b(u,v)为边的流量下界,c(u,v)为边的流量上界,f(u,v)为边的实际流量,g(u,v)为边的自由流,即g(u,v) = f(u,v) - b(u,v)

无源汇有上下界可行流

对于一个在无源汇有上下界网络的可行流,任意边应满足上下界限制

b(u,v) \le f(u,v) \le c(u,v) \Rightarrow 0 \le g(u,v) \le c(u,v) - b(u,v)

于是我们把原图每条边容量转化为c(u,v) - b(u,v)。这样就可以了吗?注意到既然是网络流,必须要满足网络流的性质,对于任意结点x需满足流量平衡条件

\begin{aligned} \sum_{i} {(b(i,x) + g(i,x))} &= \sum_{j} {(b(x,j) + g(x,j))} \Rightarrow \\ \sum_{i} {b(i,x)} - \sum_{j} {b(x,j)} &= \sum_{j} {g(x,j)} - \sum_{i} {g(i,x)} \end{aligned}

对于转化后的网络,可以保证对任意x\sum_{j} {g(x,j)} - \sum_{i} {g(i,x)} = 0,但是作为已知条件,我们显然无法保证对于任意网络都有\sum_{i} {b(i,x)} - \sum_{j} {b(x,j)} = 0,这就破坏了流量平衡条件。

考虑做一些转化。记du(x) = \sum_{i} {b(i,x)} - \sum_{j} {b(x,j)}。建立超级源汇s',t',当du(x) \gt 0时,我们可以强行给结点x增加流出流量,使其满足流量平衡条件。我们从s'x连一条容量为du(x)的边,设其满流,此时对于结点x

\begin{aligned} \sum_{i} {(b(i,x) + g(i,x))} &= \sum_{j} {(b(x,j) + g(x,j))} + du(x) \Rightarrow \\ du(x) &= \sum_{j} {g(x,j)} - \sum_{i}{g(i,x)} + du(x) \Rightarrow \\  0 &= \sum_{j} {g(x,j)} - \sum_{i}{g(i,x)} \end{aligned}

类似地,当du(x) \lt 0时,给结点x增加流入流量,即从xt'连一条容量为-du(x)的边。

在建好的新图上运行s' - t'最大流。如果此时存在任意附加边没有满流,说明无法满足流量平衡条件,问题无解。若全部满流,说明存在可行流,且网络中的当前流即是一个可行流。

有源汇有上下界可行流

ts连下界为0,上界为无穷大的边。此时st也满足流量平衡条件。问题转化成无源汇有上下界可行流。

有源汇有上下界最大流

先求是否存在可行流。当有可行流时,想象一下一些网络的状况。所有的边都已满足下界条件,但是t连向s的边中还有一些残留的流量,同时有一些边可能还没达到上限,可以再通过一些流量。此时我们去掉超级源汇s',t',再运行一次s - t最大流,边(t,s)的流量就流出去了,即可求得满足上下界限制的最大流。

有源汇有上下界最小流

既然有了下界,网络最小流就变得有意义了(原来显然是零流)。

这次与求可行流的方法有一些区别。我们将ts的边的流量上界调整为0,即第一次我们不允许任何流量由t流向s。具体操作方法就是一开始不连ts的边。先运行一次s' - t'最大流。如果此时所有附加边满流,说明零流是网络的一个可行流,即零流是最小流。否则,我们将ts的边流量上界调整为无穷大,再运行一次s' - t'最大流,如果此时所有附加边满流,则边(t,s)当前的流量就是满足容量上下界限制的最小流;如果存在附加边没有满流,问题无解。

有源汇有上下界最小费用流

类比上述建图方法,我们通过流量平衡条件来寻找突破口。首先,我们把所有边改造成容量为c(u,v) - b(u,v),费用为w_i的边。考虑上述流量平衡等式。对于一条边(u,v),它对du(u)的贡献是-b(u,v),对du(v)的贡献是b(u,v)。就这一条边来说,我们给v增加流出流量,即s'v连容量为b(u,v),费用为w的边;同时我们给u增加流入流量,即ut'连容量为b(u,v),费用为0的边(避免重复计算)。

另外,还是要将网络改造成无源汇的以满足流量平衡条件,即ts连容量为无穷大,费用为0的边。

在改造后的新图上运行s' - t'最小费用最大流。当附加边全部满流时,所产生的费用即是答案;若没有满流,问题无解。

对于仅有下界的最小费用流,还有一种解决方法。将每条边拆成必须满足的边和自由边,前者容量b(u,v),费用为负无穷;后者容量c(u,v)-b(u,v),费用为w_i。由于费用流会优先选择费用较小的增广路,所以在出现正权增广路时停止算法即可,因为此时一定满足了所有必须满足的边。在费用流运行结束后再将去掉的费用加回来即可。这种方法也是很不错的,但是在图不保证为DAG时有可能产生负环。

[本篇文章中有些结论可能是我口胡,并没有严格证明。若存在反例,请在评论中指出。]