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

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

2018 年 3 月 25 日 11:59


文章目录

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

(2018.08.29 更新此文,你没有阅读过的船新版本)

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

网络流的定义

“网络流(network-flows)是一种类比水流的解决问题方法。”
假设现在有一张有限的有向图 G,这张图上有一个源点 ss,一个汇点 tt,每条边都有一个最大流量(即容量),就像复杂的水管网络。现在我们定义几个概念:

  • 源点(Sources):一切流量流入的点。
  • 汇点(Sinks):所有流量最终汇聚到的点。
  • 容量(Capacity):一条边的最大流量。
  • 残量(Residual Capacity):容量与流量之差。

网络流的三大基本性质

网络流任何时刻总满足以下三条性质:
1. 容量限制(Capacity Constraints)f(u,v)c(u,v)f(u,v)≤c(u,v),即一条边的流不能超过它的容量。(不然水管就要被挤爆了……)
2. 斜对称(Skew Symmetry)f(u,v)=f(v,u)f(u,v)=-f(v,u),即由 uuvv 的净流必须是由 vvuu 的净流的相反。假设有 xx 的流量从 uu 流到 vv,那么就相当于有 x-x 的流量从 vv 流到 uu
3. 流守恒(Flow Conservation):对于除了源点 ss 和汇点 tt 以外的所有点,都满足:

\displaystyle \sum_{p\in G} f(p,u)= \sum_{q\in G} f(u,q)

也就是说任何一个点的入流等于其出流,源点和汇点除外。

最大流问题

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

Edmonds-Karp 算法

Edmonds-Karp 算法(简称EK)的主要步骤如下:

  1. 找到一条源点到汇点的路径(其中每条边残量都要大于0)(这样的路径就是增广路(Augmenting Path)),并找出这条路径上每条边残量最小值 minmin
  2. 将这条路径上每条边残量减去 min,将每条边的反向边加上 minmin(因为我们这条增广路是“随便找”的,不能保证解最优;将反向边加上 minmin 相当于提供了“反悔”的机会),并将答案累计上 minmin
  3. 重复以上过程,直到从 sstt 没有增广路为止。

(由于我太懒EK算法似乎在任何情况下都没有优化了的 Dinic 好,这里就不给出代码了……)

如何存储边

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

Dinic 算法

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

Edmonds-Karp 慢在哪里

因为 EK 算法中走到各个点没有一定的顺序,可以理解为“任意”的,所以会出现一定的问题。假设从 ss 有两条路径走到 xx(假设 xx 是增广路上的一个点),假设这两条路径中最小的残量分别为 min1min1min2min2,如果 min2min2 更大,我们应该选择 min2min2 这条路径,但是根据 EK 的处理方法我们会选择 min1min1,这样会导致重复处理。所以 EK 算法就会慢。

如何解决这个问题呢?Dinic 算法引入了“分层图”这个东西。

分层图

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

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=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;//初始流量为正无穷 
    }
}

当前弧优化

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

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

(洛谷模版题“最大网络流”(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


暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)