Chlience

【算法】网络流总结 -Boshi
网络流基本手段网络流基本概念我们可以将网络流类比为一些单向通水的水管组成的网络。以下的概念都将这样类比。节点v:水...
扫描右侧二维码阅读全文
28
2019/02

【算法】网络流总结 -Boshi

网络流基本手段

网络流基本概念

我们可以将网络流类比为一些单向通水的水管组成的网络。以下的概念都将这样类比。

  • 节点v:水管的交点(交点没有流量限制)。英文vertex的首字母。
  • 弧e:水管(具有流量限制)。英文edge的首字母。
  • 容量c(u,v):水管的最大流速。英文capacity的首字母。
  • 流量f(u,v):水管当前的流速。英文flow的首字母。
  • 流F(S,T):水管网络仅从S进水,从T出水,的一个合理的流量方案。

下面,我们又有几个公理:

  • 弧的流量限制:$f(u,v)\leq c(u,v)$。
  • 流量平衡:节点v的进入流量等于流出流量。

然后根据这些概念,我们可以定义网络流中最重要的一个部分:

  • 最大流F(S,T)::所有流F(S,T)中S处流速最大的方案。

同时还有几个比较重要的概念:

  • 增广路P(S,T):指从S到T的一条经过的弧全部满足$f<c$的路径。
  • 残量网络G:将原图每条边的c减去f得到的图。即原图没有满流的边组成的图。

dinic算法及其优化

dinic算法是求解网络流问题的重要手段之一。基本地,它可以在最坏$O(n^2m)$的时间复杂度内求解一幅有向图内从S到T的最大流。当然,根据不同图的不同特性,这个时间复杂度往往达不到最坏,故我们可以在数据范围不是很大的情况下放心使用dinic算法。

dinic算法的基本步骤是:

  • 1.根据还有剩余流量的边生成分层网络
  • 2.重复这一个步骤:获取可行増广路,并把増广路上的边的流量同时增加到最大可行值。

重复这两个步骤,直到无法生成使ST联通的分层网络为止。这时的网络上的流量就是最大流的流量。
但是需要注意的是,为了保证dinic算法的正确性,我们在增广时需要将反向边的剩余流量对称的增加,以便算法以后的反悔。
对dinic的具体实现不多做介绍,下面着重介绍两个较为有效的优化。

当前弧优化:记录dinic算法在每一个节点尝试继续增广时增广到了哪一条边。
整体流量优化:对于每一个节点,记录可以向下流的总流量再返回。这样可以减少递归的次数。
int dep[MX],q[MX];            //分层网络的深度,bfs的队列
int bfs(int frm,int to)        //生成分层网络
{
    int h=0,t=1,x,y;
    memset(dep,0xff,sizeof(dep));
    q[++h]=frm;
    dep[frm]=0;
    while(h>=t)
    {
        x=q[t++];
        for(int i=fst[x];i!=-1;i=nxt[i])
        {
            y=e[i].v;
            if(dep[y]==-1&&e[i].c)
            {
                dep[y]=dep[x]+1;
                q[++h]=y;
            }
        }
    }
    return (dep[to]>=0);    //返回分层网络是否成功生成
}

int cur[MX];                //当前弧优化的记录数组
int dinic(int x,int mn)
{
    if(x==T)return mn;
    int y,a,now=0;
    for(int &i=cur[x];i!=-1;i=nxt[i])    //"int &i="这一句是当前弧优化的核心
    {
        y=e[i].v;
        if(e[i].c&&dep[y]==dep[x]+1)
        {
            a=dinic(y,min(mn-now,e[i].c));
            now+=a;                        //整体流量优化,记录当前节点往下流的最大流量后再返回
            e[i].c-=a,e[i^1].c+=a;        //帮助dinic反悔
            if(mn==now)return now;
        }
    }
    return now;
}

int mxflow()
{
    int tot=0;
    while(bfs(S,T))
    {
        memmove(cur,fst,sizeof(fst));
        tot+=dinic(S,+oo);
    }
    return tot;
}

网络流问题

(Level 1)

1.单源单汇最大流

直接运用dinic算法即可。

2.多源多汇最大流

建立新的源点S和汇点T,S与原图的S相连,原图的T与T相连即可。这样就用单源汇网络流代替了多源汇网络流。这种在图的构造上做文章的例子非常多见,而且也是非常有效、常用、深奥的学问。

3.二分图的最大匹配

即求解二分图两部分间最多有几条不共点的边相连。
将二分图左右两部分间的边容量设为1,求解从左到右的最大流即可。

4.路径覆盖问题

求如何用最少的路径覆盖一个图。

路径不可以相交:显然,如果给我们n条路径,我们一定可以覆盖整张图。如果路径可以合并,我们就可以用更少的路径覆盖图。下求最多可以合并几条路径:将原图的每个点拆成两个点$v_1,v_2$,每一条边$(u,v)$边成$u_1,v_2$。求所有1类点和2类点的最大匹配即可。

路径可以相交:如果两个点可以互相到达,那么这两个点就可以被一条路径覆盖。因此先将原图中所有可以互相到达的点之间补全边,然后再作第一种路径覆盖。

(Level 2)

1.有上下界网络流:

a.有上下界最大流

如果一条边的流量只能在[a,b]的范围内,我们也可以通过对图的修改将这个问题转化为普通的上界网络流。

分析一条边的流量$x(x\in [a,b])$,那么$x$一定可以表示为$x=a+(x-a),(x-a)\le(b-a)$,那么我们想办法把x的下界去掉即可。
如果这一条边$(u,v)$的流量在可行范围之内,那我们可以先将这条边流入流量中为$a$的部分短接到$T$,即$(u,T)=a$,这条短接的边一定满流。同时将$S$也短接一条为$a$的边到$v$,即$(S,v)=a$,同样是必须满流的边,此时我们就可以放心设置$(u,v)=b-a$了。这样,我们巧妙地躲过了下界的限制。还有,这里说的$S$和$T$不是原图的$s$和$t$,我们还需要将$(S,s)=+\infty$,$(t,T)=+\infty$连接,组成一幅完整的网。现在就可以顺利求出$F(S,T)$了。

还余下一个问题,如何通过新图的流量计算原图的流量呢?我们讨论一下:

  • 几条短接的边没有满流:原图无解。
  • 几条短接的边满流,所有边的下界和为$W$:则原图的最大流$F(s,t)=F(S,T)-W$。

具体原因可以感性地证明$F(S,T)=F(s,t)+W$:首先$F(s,t)$的流量包含在了$F(S,T)$中,每个$a$又由于短接而全部被计算了一次。又因为$F(s,t)$和$W$并不冲突,所以$F(S,T)=F(s,t)+W$。

b.有上下界循环可行流

循环流的定义是:每一条边的流量在界定范围内,每个节点的收支平衡。

为了构造循环流,我们可以先将下界限制去除。即:先强行让每条边的流量就是最小流。这样的结果就是满足了边的限制,但没有满足点的限制,下面我们将通过基础网络流使点的限制也满足。

由于节点的收支不平衡,所以有的节点会由于收大于支而出现囤积的流量,另外的则会缺少流量。我们下面的工作将是用每条边剩余的可行流量把存在囤积流量的节点的流量分配到缺少流量的节点,即“劫富济贫”。

具体怎么做呢?感性地,将边想象成管道。每条管道被拆成了两条并行的管道$A_i,B_i$,$A$用来运输流量下界,$B$运输下界与上界之间的那部分流量。当我们强制使$A$满流时,每个节点多余或不足的流量$S_i$将利用$B$管道运输。

而上面这个情景与下面这个是等同的:

有一个由$B$种管道组成的管道网络,每个节点从外界输入或向外界输出$S_i$的流量,问$B$管道能否运输外界给予的流量。

这样一想,就很清楚了。建图方法也显而易见了。

  • 先让每条边满足下界,求出每个节点的$S_i=\sum in-\sum out$
  • 原图的$f(u,v)\in [a,b]$对应新图的$f(u,v)\in [0,b-a]$
  • 新图建立边$f(S,i)=S_i(S_i>0)$ 或 $f(i,T)=|S_i|(S_i<0)$

如果新图的$MaxFlow(S,T)$使的所有步骤3建立的边都满流,则原图存在循环可行流,每条边的流量为新图该边的流量+该边下界流量。

c.有上下界最小流

该最小流的定义一般是指某一条边上流量的最小化。

方法1:

先明确一个定理:

先计算原图最大流,再添边计算流量变化,与先添边,再一起计算总流量相比,可以保证添的边上流量最小.

这样,我们就可以利用循环流求得最小流。

我们可以新建一条边$(T,S)=+\infty$,求出$(T,S)$上流量最小的循环流。利用上面的定理,可以将有上下界循环可行流的步骤拆成两步,第一步不加边$(T,S)$按照完整步骤求循环流,再加上边$(T,S)$重复求循环流的完整步骤。这样即可求出原图的最小循环流。

方法2:

加边$(T,S)$,求出一个循环可行流,然后删除边$(T,S)$,从T到S反向求最大流。求最大流即将不必要的流量尽可能退回。

2.最小(大)费用最大流问题

增广路的求解不在使用dinic算法,而是用SPFA每次寻找最短(长)的一条边。根据网络流的贪心原则,我们最终找到的一定也是最大流。如下是一个最小费用最大流的代码片段。

int q[MX],pre[MX],dis[MX],inq[MX];
int spfa(int *flow,int *cost)
{
    int h=0,t=1,x,y,now=pre[T],mxf=+oo,cst=0;
    memset(dis,0x3f,sizeof(dis));
    memset(inq,0,sizeof(inq));
    memset(pre,0,sizeof(pre));
    q[++h]=S;dis[S]=0;pre[S]--;
    while(h>=t)
    {
        x=q[(t++)%MX];
        inq[x]=0;
        for(int i=fst[x];i!=-1;i=nxt[i])
        {
            y=e[i].v;
            if(e[i].c&&dis[y]>dis[x]+e[i].w)
            {
                dis[y]=dis[x]+e[i].w;
                pre[y]=i;                //记录节点的前驱
                if(!inq[y])q[(++h)%MX]=y,inq[y]=1;
            }
        }
    }
    if(dis[T]>+oo)return 0;                //没有増广路
    while(now!=-1)                        //找到增广路上的最小权边权
    {
        mxf=min(mxf,e[now].c);
        cst+=e[now].w;
        now=pre[e[now].u];
    }
    now=pre[T];
    while(now!=-1)                        //增广后修改边的流量
    {
        e[now].c-=mxf;
        e[now^1].c+=mxf;
        now=pre[e[now].u];
    }
    *flow+=mxf,*cost+=cst*mxf;
    return 1;yi
}

int mcf()                                //minimum_cost_flow
{
    int flow=0,cost=0;
    while(spfa(&flow,&cost));
    return cost;
}
a.最小(大)费用最大流

最基础的模型,直接用上面的代码。

b.最小(大)费用最大循环流

比如最大费用循环可行流,可以不停用SPFA/BELLMAN_FORD找最大权环,将这个环增加流量。这样可以保证最后找到最大费用的循环流。

c.最小(大)费用有上下界循环可行流

先建立循环可行流的图$G_0$。然后建立超级源汇处理每个节点上的流量盈余和流量赤字。当超级源汇间的流量达到最大时,对应的就是原图$G_0$的最小(大)费用有上下界循环可行流。

3.边权变化的费用流

这类费用流的通性是:费用与流量不成线性关系。但是这种函数我们依旧可以用线性函数拟合。
例如:

  • 一条边的边权在经过一次后改为0:这条边拆成两条边,第一条容量为1,权值不变;第二条容量为$+\infty$,权值为0
  • 一条边的权值与流量成二次函数关系(整数流量):这条边拆成多条边,每条容量为1,权值分别为1,3,5,...
  • 一条边的权值与流量成二次函数关系(实数流量):二次函数关系可以用特殊方法解决,这里不在赘述。

等等等等,我们依旧不需要改变网络流算法,而是在图上做手脚。

5.动态添边的网络流

对于动态添边,动态求解的网络流,我们可以在原图添边后不重新进行所有的增广操作,而是直接在原残量网络上添边,增广。这样做并不会导致最终答案变化。我们可以这样理解:之前这条边其实一直存在,只是我们没有用它增广罢了。现在添边意味着我们可以通过它增广。这样依旧可以求出当前图的最大流、最值费用流等值。

6.二分图相关问题:

我们需要分析的是:最大匹配与最小顶点覆盖数、最小边覆盖数、最大点独立集之间的关系。

定义:

  • 最大匹配数:二分图中边集数目最大的匹配数
  • 最小顶点覆盖:用最少的点,让每条边都至少与其中一个点相连
  • 最小边覆盖:用尽量少的边,让每个点都至少与其中一个边相连
  • 最大独立集:选尽量多的点,让它们亮亮没有相连的边

a.最小顶点覆盖=最大匹配数(König定理)

定理证明:

设最大匹配数为$n$,最小顶点覆盖为$m$。

为了证明的方便,我们把最小定点覆盖中的点叫做“黑点”,反之叫做白点。

定义$M(s)​$为与$s​$相邻的所有点的集合。

首先我们证明$m\geq n​$:如果从最大匹配看最小顶点覆盖,那么最大匹配中的每一条边都没有公共顶点,故覆盖它们至少需要n条边,即$m\geq n​$。

我们再证明 $m\leq n$ :我们尝试为每个黑点一条边,且分配的边两两不相交。我们先考虑怎么为左边的黑点分配边。运用反证法:如果在分配过程中出现了问题,说明存在一个左边的黑点的子集$S$,与右边的与他们联通的白点集合$T$不存在完美匹配,根据霍尔定理,这也说明存在$s\subseteq S$,$|M(s)|<|s|$,这时,我们可以将$s$染白,将$M(s)$染黑,此时最小顶点覆盖变小,与题设矛盾。因此,我们一定可以给每个黑点分配两两不相交的边,这些边构成一个匹配。所以$m\leq n$。

那么,我们就推出了:$m=n​$,也就是说二分图的最小顶点覆盖=最大匹配数。

当然,这只是比较感性的证明,更严谨的证明可以参考König定理

构造:

另外,根据König定理,我们可以得到输出最小顶点覆盖的方案的算法(如在UVa11419中的应用)。

首先,对于任意一个匹配,肯定存在一个最小顶点覆盖,满足这些点都是匹配边的端点。因此,我们可以用基础算法求出二分图的一个匹配,再根据这个匹配求出最小顶点覆盖。

对于图中所有的非匹配点$a$,与它相邻的所有匹配点$b$都必须被选择。选择了$b$,所有与这些匹配点相邻的点$c$就可以不选择,实际上是一定不用选择,因为与$c$相邻的点一定都是匹配点。为什么呢?如果存在一个非匹配点$d$与这个点相邻,就可以找到一条新的增广路$a-b-c-d$,最大匹配就可以变得更大。因此这样$dfs$下去,我们就可以确定每个点究竟是否需要被选。如果还剩下一些点没有被确定,说明这些点根本不与非匹配点相邻,对于它们,只要同时选左边的点即可。

b.最小边覆盖=顶点数-最大匹配数

证明:

设点数为$v$,最大匹配数为$n$,最小边覆盖为$k$,图为联通图。

先证明$k\leq v-n$:

先为每个点随便分配一条边覆盖它。每一对匹配点可以共用一条边,因此$k\leq v-n$

再证明$k\geq v-n$:

所有非匹配点一定需要一条互不相同的边才能覆盖,所有匹配点最优情况下可以每两个一对,用一条边覆盖。因此$k\geq v-n$。

构造:

匹配点用匹配边覆盖,非匹配点随便选一条非匹配边覆盖。

c.最大独立集=顶点数-最大匹配数

证明:

设最大匹配数为n,最大独立集为d。

根据定理1:n=m我们可以知道,最大匹配的边对应的2n个顶点中有n个顶点最为最小顶点覆盖,那么剩下的|V|-n个点一定会两两独立,否则其中至少有一个顶点会出现在最小顶点覆盖中,与题设不符。因此这|V|-n个顶点就是最大独立集。

构造:

也就是说,最大独立集的补集就是最小顶点覆盖。

7.子图相关问题

a.最大权独立子图

最大权独立子图也叫最大权闭合子图。

最大权独立子图指的是求有向图的一个点权和最大的子图P(可以就是原图),使原图中不存在任何一条边$(u,v),(u\in P,v\not\in P)$。
也就是说“肥水不流外人田”,我们需要找到一个只能进来不能出去的子图。

怎么做呢?我们可以先把权值按正负分类,正权点在左,编号Xi,负权点在右,编号Yi。
如果我们选则了一个正权点X,为子图增加了Xi的贡献,那么X指向的负权点Y会为子图扣除|Yi|的贡献。为了利益最大化,如果我们选择的X的贡献可以弥补Y的损失,那么我们选择X,否则我们不选X。即:贡献随讨论的X的增多一定是单调不降的。换成数学语言,对于一组{Xi},{Yi},对原图的贡献一定是$|X|-min(|X|,|Y|)$。(表述有些含糊,但是我们需要意会)。这样一来,我们就可以利用最小割来解决了。

我们建立一个新图,图中左边的点对应原图每个正权点,右边的对应原图每个负权点。如果原图存在点Xi,那么原图左边也有Xi,同时建立边(S,Xi)=|Xi|,如果原图存在点Yi,那么原图右边也存在点Yi,同时建立边(Yi,T)=|Yi|。原图所有边也都加入到新图中,权值为正无穷。这样,新图最大流(即最小割)即是求出了min(|X|,|Y|)的值。我们拿所有正权点的权值和减去F(S,T)即是最大权独立子图的权值和。

与最小顶点覆盖问题一样,这个问题的数值答案和方案答案也是有一定距离的,下面要说明如何通过最大流求得具体的最大权独立子图。

对于一个求出了最小割的图,其S点可以通过正向边和反向边到达的点为原图中被选择的点。原因:无法访问的点为被割掉的边截断的点,故我们不需要选择。反之没有被截断的点就是我们要选择的点。而且可以知道这些点权值和的确为$(\sum |Xi|)-F(S,T)$。

当然,最大权独立子图中正负权点之间的边一般设为$+\infty$,如果设为某个特定的值,也是有其实际意义的。大家可以感性理解以下这时什么意思。可以从买和租的角度理解。

b.最大密度子图

最大密度子图类似于最大权独立子图,是一个点集P和边集Q构成的子图,其中$Q=\{(u,v)|u\in P,v\in P\}$,而且$\frac{|Q|}{|P|}$最大。
简单的理解就是边数/点数最大的图。每一条边都连接这这个图中的两个点。

此题的高效求解需要结合最大权闭合子图和分数规划的思想,故也出现在了这篇文章里。

设原图中密度($|E|/|V|$)大于等于x的子图的数量为num(x),那么num函数一定随x递增而递减。所以我们可以用二分法求这个函数值恰好不为0的x值。

如果我们需要判定是否存在密度为x的子图,我们可以用以下的方法:

由于每选择了一条边,与它相连的点必须被选择。那么如果我们设边权为1,点权为-x,若我们按照这种策略找到了权值和大于0的子图,则证明存在密度为x的子图,反之不存在。

所以我们可以建立二分图,通过求解最大权闭合子图获得答案。建立一个二分图,左边的顶点Xi对应原图的边,连边(S,Xi)=1,右边的顶点Yi对应原图的点,连边(Yi,T)=x。按照最大权闭合子图的算法,如果你得知最大权为0时(即最大权的子图就是屁都不选),你就要含泪调小二分上界继续查找更小的x,反之你可以自信地调大下界,尝试更大的x。这样,我们通过对x的二分+判定,找到了满足要求的x,使num(x)恰好不为0。由于这时的x可能为小数,所以我们需要对实数进行二分,在实数意义下跑网络流,此时需注意eps等的设定。

其他

a. Dilworth定理

图的最长反链长度等于最小链覆盖。

该定理是针对什么鬼偏序集上的。其具体内容是:反链是一种偏序集,其任意两个元素不可比;而链则是一种任意两个元素可比的偏序集。Dilworth定理说明,存在一个反链A与一个将序列划分为链族P的划分,使得划分中链的数量等于集合A的基数。

链,我们可以具象地理解为图上的一条有向边连成的路,因此反链就是图上的一组点,两两不可达。

证明:略

b.霍尔定理

二分图的完美匹配存在的充要条件是:二分图左部任意k个元素在右部共有k个以上的相邻元素。

证明:

充分性:

使用反证法,如果条件成立,但是二分图不存在完美匹配,说明图的左部一定存在至少一个非匹配点,从这个点出发,找右部的相邻点,如果条件成立,我们一定可以一直找下去,永无止境。如果我们停下,就说明条件不成立,或者存在一条增广路,总之无论如何都与题设矛盾。

必要性:

显然。

Last modification:February 28th, 2019 at 04:56 pm

Leave a Comment