网络流最大流算法总结(Edmonds-Karp 算法+Dinic 算法)

“网络流(network-flows)是一种类比水流的解决问题方法,与线性规划密切相关。网络流的理论和应用在不断发展,出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。”
——百度百科

网络流是信息学竞赛中的常见题型了。

网络流的定义

“网络流(network-flows)是一种类比水流的解决问题方法。”假设现在有一张有限的有向图 G,这张图上有一个源点s,一个汇点t,每条边都有一个最大流量(即容量),就像复杂的水管网络。定义几个概念:
– 源点:一切流量流入的点。
– 汇点:所有流量最终汇聚到的点。
– 容量:一条边的最大流量。
– 残量:容量与流量之差。

网络流的三大基本性质

网络流任何时刻总满足以下三条性质:
1. 容量限制 (Capacity Constraints):f(u,v)≤c(u,v),即一条边的流不能超过它的容量。(不然水管就要被挤爆了……)
2. 斜对称 (Skew Symmetry):f(u,v)=-f(v,u),即由u到v的净流必须是由v到u的净流的相反。假设有x的流量从u流到v,那么就相当于有-x的流量从v流到u。
3. 流守恒 (Flow Conservation):对于除了源点s和汇点t以外的所有点,都满足: \displaystyle \sum_{p\in G} f(p,u)= \sum_{q\in G} f(u,q)
也就是说任何一个点的入流等于其出流,源点和汇点除外。

最大流问题

现在假设有无限的流量从源点s流入,我们要求出最后流到汇点t的最大流量(注意任何时候上面三个条件都要满足)。
对于最大流问题可以用 Edmonds-Karp 算法或 Dinic 算法解决。后者是前者的优化,但是前者更易于理解,所以我们先了解 Edmonds-Karp 算法。

Edmonds-Karp 算法

Edmonds-Karp 算法(简称EK)的主要步骤如下:
1. 找到一条源点到汇点的路径(其中每条边残量都要大于0)(这样的路径就是增广路),并找出这条路径上每条边残量最小值 min;
2. 将这条路径上每条边残量减去 min,将每条边的反向边加上min(因为我们这条增广路是“随便找”的,不能保证解最优;将反向边加上min相当于提供了“反悔”的机会),并将答案累计上min;
3. 重复以上过程,直到从s到t没有增广路为止。
(由于我太懒EK算法似乎在任何情况下都没有优化了的Dinic好,这里就不给出代码了……)

如何存储边

要快速又节省空间地求出一条边的反向边并不简单。这里我们可以用邻接表存储(关于邻接表可以参见:SPFA算法总结):在读取边的信息的同时,add(x,y,z),add(y,x,0),这样一条边与其相邻边的边号总是相邻。我们如果从0开始存储边号,那么i的相邻边就是i^1,就是它的反向边!(^表示异或)

Dinic 算法

Dinic 算法是对 Edmonds-Karp 的优化。

Edmonds-Karp 慢在哪里

因为EK算法中走到各个点没有一定的顺序,可以理解为“任意”的,所以会出现一定的问题。假设从s有两条路径走到x(假设x是增广路上的一个点),假设这两条路径中最小的残量分别为min1、min2,如果min2更大,我们应该选择min2这条路径,但是根据EK的处理方法我们会选择min1,这样会导致重复处理。所以EK算法就会慢。
如何解决这个问题呢?Dinic 算法引入了“分层图”这个东西。

分层图

对于s开始通过BFS构造分层图,这样可以保证日后DFS使用的从s到达x的路径都是“最短路”(也就是最优路径)。

Dinic 算法核心代码

inline bool BFS(){//这个函数的作用是构造分层图同时返回有无增广路 
    memset(deep,0,sizeof(deep));
    deep[s]=1;//源点的深度为1 
    int head=0,tail=1;que[tail]=s;
    while (head!=tail){
        head++;
        for (int i=lnk[que[head]];i!=-1;i=nxt[i]) if (w[i]>0&&deep[son[i]]==0) deep[son[i]]=deep[que[head]]+1,que[++tail]=son[i];
    }
    if (deep[t]==0) return 0;//如果汇点深度为0说明没有被修正到,也就是说没有增广路 
    return 1;
}
inline int DFS(int x,int now){//x为当前点,now为当前流量 
    if (x==t) return now;
    for (int i=lnk[x];i!=-1;i=nxt[i]) if (deep[son[i]]==deep[x]+1&&w[i]!=0){
        int nxtd=DFS(son[i],min(now,w[i]));
        if (nxtd>0){
            w[i]-=nxtd;
            w[i^1]+=nxtd;//反向边加  
            return nxtd;//向上传递 
        }
    }
    return 0;
}
inline void Dinic(){
    while (BFS()){
        while (int now=DFS(s,1<<30)) ans+=now;//初始流量为正无穷 
    }
}

当前弧优化

Dinic 算法仍然可以优化,这个优化称为“当前弧优化”。基于这样一个事实:任何一条增广路中一条边不会存在两次。所以我们可以加一个数组cur[x]表示当前x这个点循环到的边。(具体参见完整代码)

完整代码(含当前弧优化)

(经洛谷模版题“最大网络流”(P3376)测评通过)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10005,maxe=200005;
int n,m,s,t,tot=-1,ans=0,nxt[maxe],son[maxe],w[maxe],deep[maxn],lnk[maxn],que[maxn],cur[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void add(int x,int y,int z){
    tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline bool BFS(){//这个函数的作用是构造分层图同时返回有无增广路 
    memset(deep,0,sizeof(deep));
    deep[s]=1;//源点的深度为1 
    int head=0,tail=1;que[tail]=s;
    while (head!=tail){
        head++;
        for (int i=lnk[que[head]];i!=-1;i=nxt[i]) if (w[i]>0&&deep[son[i]]==0) deep[son[i]]=deep[que[head]]+1,que[++tail]=son[i];
    }
    if (deep[t]==0) return 0;//如果汇点深度为0说明没有被修正到,也就是说没有增广路 
    return 1;
}
inline int DFS(int x,int now){//x为当前点,now为当前流量 
    if (x==t) return now;
    for (int i=cur[x];i!=-1;i=cur[x]=nxt[i]) if (deep[son[i]]==deep[x]+1&&w[i]!=0){
        int nxtd=DFS(son[i],min(now,w[i]));
        if (nxtd>0){
            w[i]-=nxtd;
            w[i^1]+=nxtd;//反向边加  
            return nxtd;//向上传递 
        }
    }
    return 0;
}
inline void Dinic(){
    while (BFS()){
        for (int i=1;i<=n;i++) cur[i]=lnk[i];
        while (int now=DFS(s,1<<30)) ans+=now;//初始流量为正无穷 
    }
}
int main(){
    memset(lnk,-1,sizeof(lnk));//因为边号从0开始存储,所以-1表示没有边 
    memset(nxt,-1,sizeof(nxt));
    n=read();m=read();s=read();t=read();
    for (int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,0);//构造反向边并且其边号与正向边相邻 
    }
    Dinic();
    printf("%d\n",ans);
    return 0;
}

模板题

洛谷3376
POJ1273


参考

网络流_百度百科
网络流 – 维基百科,自由的百科全书
Dinic算法(研究总结,网络流)
网络流算法+例题整理 – CSDN博客
网络流【最大流&&最小割】——一篇简单易懂的博文
网络流和棒球赛淘汰问题 | Matrix67: The Aha Moments

本文采用 BY-NC-SA 4.0 协议,欢迎转载。如有错误欢迎指出。
本文链接: https://skywt.cn/posts/network-flows/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。