Dinic学习笔记

网络流是啥不用我说了吧

增广路定理不用我说了吧

Dinic就是分层然后只在层间转移，然后就特别快，$$O(N^2M)$$

伪代码：

function dinic

    int flow = 0 ;

    while bfs() do

        memsets()

        while int val = dfs() do

            flow += val;

    return flow

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std ;

#define MAXN 1000005

int head[MAXN],ver[MAXN*4],edge[MAXN*4],Next[MAXN*4],tot=-1,s,t ;

int dep[MAXN],cur[MAXN] ;

int n,m ;

void init(){

    tot = -1 , memset(head,-1,sizeof(head)),memset(Next,-1,sizeof(Next)) ;

}

void _add(int u,int v,int w){

    ver[++tot]=v,

    edge[tot]=w,

    Next[tot]=head[u],

    head[u]=tot ;

}

void add(int u,int v,int w){

    _add(u,v,w),

    _add(v,u,0) ;

}

int bfs(){

    memset(dep,0,sizeof(dep)) ;

    queue<int> Q ;while(!Q.empty()) Q.pop() ;

    Q.push(s) ; dep[s] = 1 ;

    while(!Q.empty()){

        int v=Q.front() ; Q.pop() ;

        for(int i=head[v];i!=-1;i=Next[i]){

            //printf("Bfs: at dot %d\n",ver[i]) ;

            //for(int j=1;j<=MAXN*10;++j) ;

            if(dep[ver[i]] == 0 && edge[i]>0)

                dep[ver[i]] = dep[v]+1 , Q.push(ver[i]) ;

        }

    }

    if(!dep[t]) return 0 ;

    return 1 ;

}

int dfs(int u,int f){

    if(u == t) return f ;

    for(int& i=cur[u];i!=-1;i=Next[i]){

        if(dep[ver[i]] == dep[u]+1 && edge[i]!=0){

            int di = dfs(ver[i],min(edge[i],f)) ;

            if(di > 0){

                edge[i] -= di , edge[i^1] += di ;

                return di ;

            }

        }

    }

    return 0 ;

}

int Dinic(){

    int flow = 0 , d = 0 ;

    while(bfs()){

        for(int i=1;i<=n;++i) cur[i] = head[i] ;

        while(d = dfs(s,0x3f3f3f3f)) flow += d ;

    }

    return flow ;

}

int main(){

    init() ;

    scanf("%d%d%d%d",&n,&m,&s,&t) ;

    for(int i=1;i<=m;++i){

        int x,y,z ; scanf("%d%d%d",&x,&y,&z) ; add(x,y,z) ;

    }

    printf("%d\n",Dinic()) ;

}

巴特西

Dinic学习笔记

最新文章

热门文章