网络流入门之最大流

摘要

网络流是强有力的图论算法之一,其算法本身不难,但是所解决的问题却千变万化。简而言之,网络流的难点在于建模。本文则注重讲解网络流的最大流算法。

2019.6.14:收编精选文章。

网络

网络是指一个有向图 .

每条边 都有一个权值 ,称之为容量(Capacity),当 时有 .

其中有两个特殊的点:源点 s 和汇点 t。 .

流,就是水流啦。我们把网络流理解为从源点到汇点的水流。这个水流被分为若干股,几经周转最后逐渐回合到汇点。形式化的定义,设 是定义在二元组 上的实数函数且满足

  1. 容量限制
  2. 斜对称性
  3. 流守恒性

那么 称为网络 的流函数。对于 称为边的流量 称为边的剩余容量。整个网络的流量为 ,即从源点发出的所有流量之和。下图即为一个网络图:

p1

注:流函数的完整定义为

是不是一脸懵逼 emmm

我们这样理解,每一条边其实还对应着一条反向的虚边。这个虚边在原图中是不存在的,但在我们实现这个算法的时侯是会建出来的,目的就是化归对流的操作。我们知道 表示从 u 到 v 的水的流量,那么如果 ,那么 就是它的虚边。

等等!万一 同时存在呢?其实这并不影响,那么我们对这两条边都建虚边就行。

于是回到上文,对于虚边 ,就有 ,含义就是,从 u 到 v 的水的流量为 -f(v,u),这 TM 不就是废话嘛 emmm 它和 “从 v 到 u 的水的流量为 f(v,u)” 其实是对应的。

那么问题来了,既然这个虚边和实边的流的变化是对应的,那我要你虚边干甚?

我们思考算法过程。为了得到最大流,我们需要调整各边流量。增加的时侯就增加流量,减少的时侯就减少流量。但这一切都建立在有向边的基础上,意味着我们只能沿着有向边的方向增加 / 减少流量。而事实上我们可能会遇到这样的情况:在当前流的状态下,我们找不到剩余的地方(即一条路径)可以增加流量了,这时可以通过减少某些边的流量,以空出一定的空间,这样就能找到流量了。

减少流量,在虚边上就是增加流量!

于是我们把增加 / 减少流量就归一为了一种操作——增加流量。在增加的时侯,同时更新反向对应边(如果是实边就更新虚边,如果是虚边就更新实边。反向对应边一定是一实一虚,千万不要把这里的反对应向边和反平行边搞混!)的流量即可。

虚边在帮助我们找到増广路(见下文)也有很大帮助。

最大流主流的两种方法

最大化 的流函数被称为最大流。

对于公式恐惧症患者,我们说最大流就是从源点发出最多的流量。

Ford-Fulkerson 方法

注意方法和算法的区别。一定程度上,方法比算法更广义,它泛指解决问题的流程。而每个流程可以使用不同的算法完成。

该方法通过寻找增广路来更新最大流。有 主流算法

Push-Relabel 方法

该方法在求解过程中忽略流守恒性,并每次对一个结点更新信息,以求解最大流。说白了这是一个在地平线上挣扎的算法。有 的主流算法。

这玩意儿难写难调,建议不要食用(那我写这个章节干嘛)(大雾)

Edmonds-Krap 增广路算法

残存网络

对于流函数 ,残存网络 是网络 中所有结点和剩余容量大于 0的边构成的子图。形式化的定义,即 .

注意,剩余容量大于 0 的边可能不在原图 中(根据容量、剩余容量的定义以及流函数的斜对称性得到)

其实听名字可以想明白,就是那些还剩了流量空间的边构成的图,也包括虚边。

增广路

在原图 中若一条从源点到汇点的路径上所有边的剩余容量都大于 0,这条路被称为增广路。

或者说,在残存网络 中,一条从源点到汇点的路径被称为增广路。

算法过程

显然可以让一股流沿增广路从源点走到汇点,增大整个网络的流量

EK 算法通过 BFS 寻找增广路,直到网络中不存在增广路为止。

EK 算法同时会考虑 的反向边 ,当 ,根据斜对称性, 也属于剩余容量大于 0 的边,在 BFS 时也会遍历。我们使用异或运算成对变换的技巧来访问反向边

EK 算法只维护残存网络,不维护原图

p2

图中的边权表示边的剩余容量,省略了剩余容量为 0 的边,并展示了寻找增广路的过程。最终 P6 不存在增广路,最大流为 7.

EK 算法复杂度 ,能处理 的网络

[LuoguP3376]【模板】网络最大流

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4+4,M=1e5+5,INF=0x3f3f3f3f;
int n,m,s,t,maxflow;
// 前向星存图
struct qxx{int nex,t,v;};
qxx e[M*2];
int h[N],cnt=1;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}

bool vis[N];
int incf[N],pre[N];
bool bfs(){memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s),vis[s]=1,incf[s]=INF,incf[t]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nex){
            const int &v=e[i].t,&w=e[i].v;
            if(vis[v]||w==0)continue;// 排除访问过的点或剩余容量为 0 的边
            incf[v]=min(incf[u],w);// 记录增广路上最小剩余容量
            q.push(v),vis[v]=1,pre[v]=i;// 记录前驱边的编号
        }
    }
    return incf[t];
}
void update(){
    maxflow+=incf[t];// 更新最大流
    for(int u=t;u!=s;u=e[pre[u]^1].t){
        e[pre[u]].v-=incf[t],e[pre[u]^1].v+=incf[t];// 反向边的剩余容量
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_path(u,v,w);add_path(v,u,0);// 反向边,初始的剩余容量为 0
    }
    while(bfs())update();
    printf("%d",maxflow);
    return 0;
}

Dinic 算法

分层图

以源点为起点在残存网络中做 BFS,在 BFS 的过程中,我们标记每个结点的层次 ,表示从 经过的最少的边数。

分层图则是 的所有结点和满足 的边 构成的子图。

算法过程

EK 算法在寻找增广路的过程中,可能会遍历整个残存网络,导致寻找增广路的复杂度偏高

Dinic 算法通过不断构造分层图,在分层图上寻找增广路并更新的方式求解最大流

即 Dinic 算法遵循以下步骤,直到源点汇点不连通:

  1. 构造分层图
  2. 在分层图上求增广路并更新最大流,直到找不到增广路为止

时间复杂度 .

核心代码

const int N=1e4+4,M=1e5+5,INF=0x3f3f3f3f;
int n,m,s,t,maxflow,d[N];
bool bfs(){// 如果源点汇点不连通返回 0
    memset(d,0,sizeof(d));
    queue<int> q;
    q.push(s),d[s]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nex){
            const int &v=e[i].t,&w=e[i].v;
            if(!d[v]&&w)d[v]=d[u]+1,q.push(v);
        }
    }
    return d[t];
}
int dinic(int u,int flow){// 到达 u 时可以增广的流量
    if(u==t)return flow;
    int k,rest=flow;// 增广完 u 后剩下的流量
    for(int i=h[u];i&&rest;i=e[i].nex){
        const int &v=e[i].t,&w=e[i].v;//rest>0
        if(!w||d[v]!=d[u]+1)continue;
        k=dinic(v,min(rest,w));
        if(k)e[i].v-=k,e[i^1].v+=k,rest-=k;
        else d[v]=0;//v 已满流,从分层图中删除
    }
    return flow-rest;// 减掉剩下的流量
}
// 调用:while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i;

推送 - 重贴标签算法

能看到这只能说明您很有耐心了

但我仍强烈建议你右转看我写的 费用流 去了 emmm这玩意儿超不实用的(大雾)

推送 - 重贴标签算法通过对单个结点的更新操作,直到没有结点需要更新来求解最大流

算法过程维护的流函数不一定保持流守恒性,对于一个结点,我们允许进入结点的流超过流出结点的流,超过的部分被称为结点 超额流

,称结点 溢出.

推送 - 重贴标签算法维护每个结点的高度 ,并且规定溢出的结点 如果要推送超额流,只能向高度小于 的结点推送;如果 没有相邻的高度小于 的结点,就修改 的高度(重贴标签).

高度函数

准确地说,推送 - 重贴标签维护以下的一个映射

  • .

则称 是残存网络 的高度函数。

引理 1:设 上的高度函数为 ,对于任意两个结点 ,如果 ,则 不是 中的边。

算法只会在 的边执行推送。

推送 -Push

适用条件:结点 溢出,且存在结点 ,则 push 操作适用于 .

于是,我们尽可能将超额流从 推送到 ,推送过程中我们只关心超额流和 的最小值,不关心 是否溢出。

如果 在推送完之后满流,将其从残存网络中删除

重贴标签 -Relabel

适用条件:如果结点 溢出,且 ,则 relabel 操作适用于 .

则将 更新为 即可。

初始化

上述将 充满流,并将 抬高,使得 ,因为 ,而且 毕竟满流,没必要留在残存网络中;上述还将 初始化为 的相反数。

通用执行框架

无需按照特定顺序,执行以下过程:

  • 只要存在结点 满足 push 或 relabel 的条件,就执行对应的操作。

如图,每个结点中间表示编号,左下表示高度值 ,右下表示超额流 ,结点颜色的深度也表示结点的高度;边权表示 ,绿色的边表示满足 的边 (即残存网络的边 ):

p1

整个算法我们大致浏览一下过程,这里笔者使用的是一个暴力算法,即暴力扫描是否有溢出的结点,有就更新

p2

最后的结果

p3

可以发现,最后的超额流一部分回到了 ,且除了源点汇点,其他结点都没有溢出;这时的流函数 满足流守恒性,为最大流,即 .

核心代码

const int N=1e4+4,M=1e5+5,INF=0x3f3f3f3f;
int n,m,s,t,maxflow,tot;
int ht[N],ex[N];
void init(){// 初始化
    for(int i=h[s];i;i=e[i].nex){
        const int &v=e[i].t;
        ex[v]=e[i].v,ex[s]-=ex[v],e[i^1].v=e[i].v,e[i].v=0;
    }
    ht[s]=n;
}
bool push(int ed){
    const int &u=e[ed^1].t,&v=e[ed].t;
    int flow=min(ex[u],e[ed].v);
    ex[u]-=flow,ex[v]+=flow,e[ed].v-=flow,e[ed^1].v+=flow;
    return ex[u];// 如果 u 仍溢出,返回 1
}
void relabel(int u){ht[u]=INF;
    for(int i=h[u];i;i=e[i].nex)if(e[i].v)ht[u]=min(ht[u],ht[e[i].t]);
    ++ht[u];
}

HLPP 算法

最高标号预流推进算法(High Level Preflow Push)是基于推送 - 重贴标签算法的优先队列实现,该算法优先推送高度高的溢出的结点,算法算法复杂度 .

具体地说,HLPP 维护以下过程:

  1. 初始化(基于推送 - 重贴标签算法)
  2. 选择溢出结点(除 )中高度最高的结点 ,并对它所有可以推送的边进行推送;
  3. 如果 仍溢出,对它重贴标签,回到 2.
  4. 如果没有溢出的结点,算法结束

BFS 优化

HLPP 的上界为 ,但在使用时卡得比较紧;我们可以在初始化高度的时候进行优化

具体来说,我们初始化 的最短距离;特别地, .

在 BFS 的同时我们顺便检查图的连通性,排除无解的情况

GAP 优化

HLPP 推送的条件是 ,而如果在算法的某一时刻, 的结点个数为 0,那么对于 的结点就永远无法推送超额流到 ,因此只能送回 ,那么我们就在这时直接让他们的高度变成 ,以尽快推送回 ,减少重贴标签的操作

[LuoguP4722] 【模板】最大流 加强版 / 预流推进

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4+4,M=2e5+5,INF=0x3f3f3f3f;
int n,m,s,t;

struct qxx{int nex,t,v;};
qxx e[M*2];
int h[N],cnt=1;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);}

int ht[N],ex[N],gap[N];// 高度;超额流;gap 优化
bool bfs_init(){memset(ht,0x3f,sizeof(ht));
    queue<int> q;
    q.push(t),ht[t]=0;
    while(q.size()){// 反向 BFS, 遇到没有访问过的结点就入队
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
            if(e[i^1].v&&ht[v]>ht[u]+1)ht[v]=ht[u]+1,q.push(v);
        }
    }
    return ht[s]!=INF;// 如果图不连通,返回 0
}
struct cmp{bool operator()(int a,int b)const{return ht[a]<ht[b];}};// 伪装排序函数
priority_queue<int,vector<int>,cmp> pq;// 将需要推送的结点以高度高的优先
bool vis[N];// 是否在优先队列中
int push(int u){// 尽可能通过能够推送的边推送超额流
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
        if(!w||ht[u]!=ht[v]+1)continue;
        int k=min(w,ex[u]);// 取到剩余容量和超额流的最小值
        ex[u]-=k,ex[v]+=k,e[i].v-=k,e[i^1].v+=k;//push
        if(v!=s&&v!=t&&!vis[v])pq.push(v),vis[v]=1;// 推送之后,v 必然溢出,则入堆,等待被推送
        if(!ex[u])return 0;// 如果已经推送完就返回
    }return 1;
}
void relabel(int u){// 重贴标签(高度)
    ht[u]=INF;
    for(int i=h[u];i;i=e[i].nex)if(e[i].v)ht[u]=min(ht[u],ht[e[i].t]);
    ++ht[u];
}
int hlpp(){// 返回最大流
    if(!bfs_init())return 0;// 图不连通
    ht[s]=n;
    memset(gap,0,sizeof(gap));
    for(int i=1;i<=n;i++)if(ht[i]!=INF)gap[ht[i]]++;// 初始化 gap
    for(int i=h[s];i;i=e[i].nex){const int v=e[i].t,w=e[i].v;// 队列初始化
        if(!w)continue;
        ex[s]-=w,ex[v]+=w,e[i].v-=w,e[i^1].v+=w;// 注意取消 w 的引用
        if(v!=s&&v!=t&&!vis[v])pq.push(v),vis[v]=1;// 入队
    }
    while(pq.size()){int u=pq.top();pq.pop(),vis[u]=0;
        while(push(u)){// 仍然溢出
            // 如果 u 结点原来所在的高度没有结点了,相当于出现断层
            if(!--gap[ht[u]])for(int i=1;i<=n;i++)
                if(i!=s&&i!=t&&ht[i]>ht[u]&&ht[i]<n+1)ht[i]=n+1;
            relabel(u);++gap[ht[u]];// 新的高度,更新 gap
        }
    }
    return ex[t];
}
int main(){scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,u,v,w;i<=m;i++){scanf("%d%d%d",&u,&v,&w);
        add_flow(u,v,w);
    }
    printf("%d",hlpp());
    return 0;
}

感受一下运行过程

HLPP

其中 执行了 ,并进行了 GAP 优化

图片制作程序

总结

Dinic 是最常用的最大流算法,而 HLPP 基本不用考虑(除非专卡网络流)。有关费用流的文章,请移步《网络流入门之费用流》


 上一篇
洛谷冬日绘板那些事 洛谷冬日绘板那些事
前言洛谷的冬日绘板从去年开始,今年是第二次了 去年其实没玩出什么来,今年我和 gavinzheng 联手自动画脚本正在画一个校徽上去 效果 脚本参考的是去年 github 的开源脚本 Enter-tainer. 见这个大佬的博客 今年的参数
2018.12.30
下一篇 
二分图漫谈 二分图漫谈
二分图一个无向连通图 中存在 满足 $\forall x,y\in B
2018.12.21
  目录