上下界网络流

2021年11月20日 阅读数:2
这篇文章主要向大家介绍上下界网络流,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

上下界网络流,顾名思义,就是每条边容量有上下界的网络流问题。针对这种较高级别的网络流大体分为如下几个问题:html

 

无源汇上下界可行流

因为没有固定的源点和汇点,也不存在什么最大/小流之说了。存在可行流的条件是全部点均知足流量平衡性质。流量平衡指的是,对于每一个点入流量=出流量。网络

若是每条边只有上界,没有下界,那只要让每条边的流量均为0,必定存在知足条件的流,若是有些边有下界,那就不必定存在知足条件的流了。url

怎么判断一张网络是否存在可行流?

首先咱们假设每条边流量均为它的下界。那么此时问题就转化为了一个只有上界的网络流问题(即普通网络流问题)。可是这么作有一个问题:下界不知足流量平衡。spa

咱们考虑利用剩余的流量去调整以知足流量平衡。具体来讲,若是某个点x的入流大于出流,咱们创建一个超级源S',创建一条$S'\rightarrow x$相应容量的边;反之,若是某个点y的入流小于出流,咱们创建一个超级汇T',创建一条$y\rightarrow T'$相应容量的边。.net

例如:htm

此时咱们在新图上跑$S'\rightarrow T'$的最大流。因为最大流保证了除源点汇点外其他点均知足流量平衡,故新图中除了S',T'其他点均知足流量平衡,那么去掉S'和T'所连的边,再加上原先的下界流量,若是满流则说明知足流量平衡,原图必然存在可行流;不然不存在。blog

模板get

怎么判断一张有源汇网络是否存在可行流?

考虑将其转化为无源汇的问题。io

将T向S连一条容量上界为inf,下界为0的边,那么若是$T\rightarrow S$这条边有流量流过,说明原图是存在可行流的。 模板

 

有源汇上下界最大流

首先按照上述方法判断出无解状况。

针对有解状况,显然当前方案是可行的,但不必定最优。咱们将上面所述的新图删去S',T'以及它们所连的边,造成一个流量不平衡的图(可是这不要紧,由于它和原图合并后是知足流量平衡的)。咱们在这张图中继续增广(增广的过程保证是平衡的),即再跑一遍最大流,获得的就是答案。

注意:第二遍的答案就是最终的答案,不用加上第一遍最大流的答案,由于第一遍搜索出来的边T到S的流量多是存在的,而第二遍搜索的时候会把这些流弹回去(反向边的存在),已经包含第一遍的流值了。

模板 

 

有源汇上下界最小流

因为流量有下界,所以是存在非零最小流的。

一样按照上述方法判断出无解状况。

注意因为要求流量最小,按照最大流那样直接增广是不行的。(感性理解:直接跑求的是最大流,而我要求最小流,显然文不对题。)

例如:

增广后的流为200,可是原图中的最小流为100,这是由于咱们没有运用循环流,也就是$2\rightarrow 1$这条边。因为咱们求的是最小流,因此事实上咱们想尽量多走一些边。

咱们先不加从T到S的边,直接增广,以下图:

而后再加那条边(注意原先边的流量仍是要保存着的),再增广一次,此时边(T,S)的剩余流量就是原图的最小流。(感性理解:先跑一次最大流把流量尽量跑完,剩下的流量就是最小流。)

模板