Dinic算法最大流入门

例题传送门

Dinic算法是网络流最大流的优化算法之一，每一步对原图进行分层，然后用DFS求增广路。时间复杂度是O(n^2*m)，Dinic算法最多被分为n个阶段，每个阶段包括建层次网络和寻找增广路两部分。

Dinic算法的思想是分阶段地在层次网络中增广。它与最短增广路算法不同之处是：最短增广路每个阶段执行完一次BFS增广后，要重新启动BFS从源点Vs开始寻找另一条增广路;而在Dinic算法中，只需一次BFS过程就可以实现多次增广。

简单来说，分为下面几步：

　　1.在剩余网络中查找是否存在从S到T的路径，同时建分层图。

　　　　分层图的层数其实就是S到i这个点需要几步。

　　2.沿着分层图多路增广。

　　　　增广时一定要满足dist[j]=dist[i]+1。

　　3.直到没有S到T的路径是结束算法。

code：

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

char tc()

{

    static char fl[],*A=fl,*B=fl;

    return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;

}

int read()

{

    char c;while(c=tc(),(c<''||c>'')&&c!='-');

    int x=,y=;c=='-'?y=-:x=c-'';

    while(c=tc(),c>=''&&c<='')x=x*+c-'';

    return x*y;

}

const int MAXN=,MAXM=;

int N,M,S,T,x,y,c,ans;

int W[MAXM*],To[MAXM*],cnt;

int l[MAXM*],h,t,dist[MAXN];

vector <int> a[MAXN];

bool BFS()

{

    h=t=;

    l[++t]=S;

    memset(dist,,sizeof(dist));dist[S]=;

        while(h<t){

            int front=l[++h];

                for(int i=;i<a[front].size();i++){

                    int to=a[front][i];

                    if(!dist[To[to]] && W[to]){

                        dist[To[to]]=dist[front]+;

                        l[++t]=To[to];

                    }

                }

        }

    return dist[T];

}

int find(int now,int x)

{

    if(now==T) return x;

        for(int i=;i<a[now].size();i++){

            int to=a[now][i];

            if(dist[To[to]]==dist[now]+ && W[to]){

                int fd=find(To[to],min(x,W[to]));

                if(fd){

                    W[to]-=fd;

                    W[to^]+=fd;

                    return fd;

                }

            }

        }

    return ;

}

int main()

{

    N=read(),M=read(),S=read(),T=read();

        for(int i=;i<=M;i++){

             x=read(),y=read(),c=read();

             W[cnt]=c,To[cnt]=y;a[x].push_back(cnt);cnt++;

             W[cnt]=,To[cnt]=x;a[y].push_back(cnt);cnt++;

        }

        while(BFS()){

            ans+=find(S,2e9);

        }

    printf("%d",ans);

    return ;

}

巴特西

Dinic算法最大流入门

最新文章

热门文章