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

/ 0评 /

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

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

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

网络流的定义

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

网络流的三大基本性质

网络流任何时刻总满足以下三条性质:
1. 容量限制(Capacity Constraints)f(u,v)≤c(u,v),即一条边的流不能超过它的容量。(不然水管就要被挤爆了……)
2. 斜对称(Skew Symmetry)f(u,v)=-f(v,u),即由 uv 的净流必须是由 vu 的净流的相反。假设有 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)(这样的路径就是增广路(Augmenting Path)),并找出这条路径上每条边残量最小值 min
  2. 将这条路径上每条边残量减去 min,将每条边的反向边加上 min(因为我们这条增广路是“随便找”的,不能保证解最优;将反向边加上 min 相当于提供了“反悔”的机会),并将答案累计上 min
  3. 重复以上过程,直到从 st 没有增广路为止。

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

如何存储边

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

Dinic 算法

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

Edmonds-Karp 慢在哪里

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

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

分层图

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

Dinic 算法核心代码

inline bool BFS(){ //这个函数的作用是构造分层图同时返回有无增广路
    CLEAR(deep);
    deep[s]=1; //源点的深度为1
    que.push(s);
    while (!que.empty()){
        int head=que.front();que.pop();
        for (int i=lnk[head];i!=-1;i=nxt[i]) if (w[i]>0&&deep[son[i]]==0) deep[son[i]]=deep[head]+1,que.push(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>
#define CLEAR(x) memset(x,0,sizeof(x))
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(){ //这个函数的作用是构造分层图同时返回有无增广路
    CLEAR(deep);
    deep[s]=1; //源点的深度为1
    que.push(s);
    while (!que.empty()){
        int head=que.front();que.pop();
        for (int i=lnk[head];i!=-1;i=nxt[i]) if (w[i]>0&&deep[son[i]]==0) deep[son[i]]=deep[head]+1,que.push(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()){
        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


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/network-flows/


发表评论

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