网络流的$\mathfrak{Dinic}$算法

网络流想必大家都知道，在这不过多赘述。网络流中有一类问题是让你求最大流，关于这个问题，许多计算机学家给出了许多不同的算法，在这里——正如标题所说——我们只介绍其中的一种——$\tt{Dinic}$

Dinic是最大流算法中综合性能比较好的一个算法，它的思想继承$Ford-Fulkerson$算法，但对FF算法有了很大的一个改进。Dinic通过分层图大大提高了算法效率，减少了许多不必要的搜索。

例题

Luogu P3376 【模板】网络最大流
正如题目所说，板子题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct zzz{
    int t,len,nex;
}e[100010<<2]; int head[10010],tot=1;
void add(int x,int y,int z){
    e[++tot].t=y;
    e[tot].len=z;
    e[tot].nex=head[x];
    head[x]=tot;
}
int vis[10010],s,t;
//每次搜索前跑一遍分层图
bool bfs(){
    queue <int> q;
    memset(vis,0,sizeof(vis));
    q.push(s); vis[s]=1;
    while(!q.empty()){
        int k=q.front(); q.pop();
        for(int i=head[k];i;i=e[i].nex){
            int to=e[i].t;
            if(!vis[to]&&e[i].len){
                q.push(to);
                vis[to]=vis[k]+1;
                if(to==t) return 1;
            }
        }
    }
    return vis[t];
}
//寻找增广路径
int dfs(int from,int flow){
    if(from==t||!flow) return flow;
    int rest=0,fl;
    for(int i=head[from];i;i=e[i].nex){
        int to=e[i].t;
        if(vis[to]==vis[from]+1&&(fl=dfs(to,min(flow-rest,e[i].len)))){
            e[i].len-=fl;
            e[i^1].len+=fl;
            rest+=fl;
            if(rest==flow) return flow;
        }
    }
    if(rest<flow)
      vis[from]=0;
    return rest;
}
//dinic
int dinic(){
    int ans=0;
    while(bfs())
      ans+=dfs(s,0x7ffffff);
    return ans;
}
inline int read()
{
    int k=0; char c=getchar();
    for(;c<'0'||c>'9';) c=getchar();
    for(;c>='0'&&c<='9';c=getchar())
      k=(k<<3)+(k<<1)+c-48;
    return k;
}
int main(){
    int 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);
    }
    printf("%d",dinic());
    return 0;
}

巴特西

网络流的$\mathfrak{Dinic}$算法

例题

最新文章

热门文章