最大流 && Dinic 算法

最大流问题

给定一个有向图，有两个特别的点$S$和$T$，每条边都有一个容量限制 ，现询问，从 $ S $ 到 $ T $ 最大可以流多少过去

第一眼看过去，跟水厂子往水管里灌水一样简单

问题在于这个东西并不好计算

有没有办法计算它呢

如果我们每次都枚举我们怎么走的话,时间复杂度是不可估计的

我们有没有办法让我们走过去的流反悔呢？

有，这里就要引入两个概念: 残余网络 && 反向边

残余网络

对于每次我们跑出来的一条流过过后以每条边现能通过的最大流量所成的网络图叫残余网络

反向边

反向边是在给算法一个反悔的机会

如果原图中有一个从 $ u $ 到 $ v $ 的边，则从 $ v $ 到 $ u $ 的边就是这条边的反向边

反向边如何后悔呢？

EK 算法

我们在每一次流过去大小为 $ t $ 一条流时，除了将原有的边上流量减去$ t $之外，也需要将其反向边的流来加上$ t $

这样以来，我们就保证以下的两点

  • 残余网络中总流量和原图相同
  • 在残余网络中走出来的流一定存在

至于怎么解释，咱的看法是，写两边就明白了，看别人的解释之后越看越懵

我们一直寻找可行的流，直到无法流到$ t $为止，已经的流过去的和就一定是一个最大流

复杂度： $O(EK(n,m))=O(m^2n)=O(TLE)$

Dinic 算法

EK算法使用bfs寻找流，但bfs寻找流的一些特性决定其不容易实现当前弧优化，以及多路增广

而且EK算法还会走回路…

这种情况下我们又要引出一个新概念: 分层图

分层图

我们以$ S $为根，可以往下走的边流大于0，然后像树一样记录每个节点的深度（多次访问取第一次）

这样以来我们可以确定以下两点:

  • 避免了回路的可能
  • 如果存在可行流，则点$ T $深度一定存在

等一下，如果我们搜索的时候都限制只能往当前节点深度+1的点去搜了，我们是不是就可以dfs了？
是的qwq

不过我们先来看一下普通的Dinic吧[Luogu P3376]

#include <cstdio>
#include <cstring>
inline int Min(int a,int b){return a<b?a:b;}
const int N=11000;
const int M=110000;
int n,m,s,t,u,v,w;
// edge start
struct edge{
    int next,to,val,un;
}e[M<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val,int un){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    e[ecnt].un=ecnt+un;
    ehead[now]=ecnt;
}
// edge end
namespace Dinic{
    int depth[N];
    int q[N],head,tail;
    inline bool bfs(){
        memset(depth,0,sizeof(depth));
        head=tail=0;
        q[head]=s;
        depth[s]=1;
        while(head<=tail){
            for(int i=ehead[q[head]];i;i=e[i].next){
                if(e[i].val>0&&depth[e[i].to]==0){
                    q[++tail]=e[i].to;
                    depth[e[i].to]=depth[q[head]]+1;
                }
            }
            head++;
        }
        if(depth[t]==0) return false;
        else return true;
    }
    int dfs(int now,int dist){
        if(now==t) return dist;
        for(int i=ehead[now];i;i=e[i].next){
            if(depth[e[i].to]==depth[now]+1&&e[i].val!=0){
                int di=dfs(e[i].to,Min(dist,e[i].val));
                if(di>0){
                    e[i].val-=di;
                    e[e[i].un].val+=di;
                    return di;
                }
            }
        }
        return 0;
    }
    inline int dinic(){
        int ans=0;
        while(bfs()){
            while(int d=dfs(s,0x7fffffff)) ans+=d;
        }
        return ans;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w,1);
        add_edge(v,u,0,-1);
    }
    printf("%d",Dinic::dinic());
}

好了，我们来讲讲两个优化: 当前弧优化 && 多路增广

当前弧优化

在当前状况下已经有一次从$ u $到$ v $的增广,则不存在第二次从$ u $到$ v $的增广

故此在我们遍历边的时候，我们可以不从ehead[now]开始，而是从上一次遍历过的边的下一个开始

namespace Dinic{
    int depth[N],rnow[N];
    int q[N],head,tail;
    inline bool bfs(){
        memset(depth,0,sizeof(depth));
        head=tail=0;
        q[head]=s;
        depth[s]=1;
        while(head<=tail){
            for(int i=ehead[q[head]];i;i=e[i].next){
                if(e[i].val>0&&depth[e[i].to]==0){
                    q[++tail]=e[i].to;
                    depth[e[i].to]=depth[q[head]]+1;
                }
            }
            head++;
        }
        if(depth[t]==0) return false;
        else return true;
    }
    int dfs(int now,int dist){
        if(now==t) return dist;
        for(int& i=rnow[now];i;i=e[i].next){
            if(depth[e[i].to]==depth[now]+1&&e[i].val!=0){
                int di=dfs(e[i].to,Min(dist,e[i].val));
                if(di>0){
                    e[i].val-=di;
                    e[e[i].un].val+=di;
                    return di;
                }
            }
        }
        return 0;
    }
    inline int dinic(){
        int ans=0;
        while(bfs()){
            for(int i=1;i<=n;i++) rnow[i]=ehead[i];
            while(int d=dfs(s,0x7fffffff)) ans+=d;
        }
        return ans;
    }
}

多路增广

很多时候在dfs的时候，我们的dist还没用完就return了，很可惜了有没有

多路增广就可以避免这些问题，我们把剩下的dist，继续往下找！

#include <cstdio>
#include <cstring>
inline int Min(int a,int b){return a<b?a:b;}
const int N=11000;
const int M=110000;
int n,m,s,t,u,v,w;
// edge start
struct edge{
    int next,to,val,un;
}e[M<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val,int un){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    e[ecnt].un=ecnt+un;
    ehead[now]=ecnt;
}
// edge end
namespace Dinic{
    int depth[N],rnow[N];
    int q[N],head,tail;
    inline bool bfs(){
        memset(depth,0,sizeof(depth));
        head=tail=0;
        q[head]=s;
        depth[s]=1;
        while(head<=tail){
            for(int i=ehead[q[head]];i;i=e[i].next){
                if(e[i].val>0&&depth[e[i].to]==0){
                    q[++tail]=e[i].to;
                    depth[e[i].to]=depth[q[head]]+1;
                }
            }
            head++;
        }
        if(depth[t]==0) return false;
        else return true;
    }
    int dfs(int now,int dist){
        if(now==t) return dist;
        int fl=0,di;
        for(int& i=rnow[now];i;i=e[i].next){
            if(depth[e[i].to]==depth[now]+1&&e[i].val!=0){
                di=dfs(e[i].to,Min(dist,e[i].val));
                if(di>0){
                    e[i].val-=di;
                    e[e[i].un].val+=di;
                    fl+=di;
                    dist-=di;
                    if(!dist) break;
                }
            }
        }
        return fl;
    }
    inline int dinic(){
        int ans=0;
        while(bfs()){
            for(int i=1;i<=n;i++) rnow[i]=ehead[i];
            while(int d=dfs(s,0x7fffffff)) ans+=d;
        }
        return ans;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w,1);
        add_edge(v,u,0,-1);
    }
    printf("%d",Dinic::dinic());
}

就这些了，那么优化过后的复杂度是什么呢
$O(Dinic(n,m))=O(n^2m)=O(AC)$

还有一个ISAP算法，不在今天的讨论之内，毕竟复杂度和Dinic差别不大且常数略大

End

]]>

《最大流 && Dinic 算法》有一个想法

  1. Pingback： Luogu P3381 最小费用最大流 – Woshiluo's Notebook

发表评论

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