最大流量dinci模板

我们知道。增广路径EK时间是在充电算法的O（n*m^2）。找到最短增广路径的时间复杂度为O（m*n^2）。这样的时间复杂度主要是寻找扩充道路。

这里也有一个演示Dinci算法，使用BFS层次结构图，然后DFS增强。

板

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define Del(a,b) memset(a,b,sizeof(a))

const int N = 1000;

const int INF = 0x3f3f3f3f;

struct Edge

{

    int from,to,cap,flow;

};

struct Dinic

{

    int n,m,s,t;

    vector<Edge> edges;

    vector<int> G[N];

    bool vis[N];

    int d[N],cur[N];

     void init(int n)

    {

        this->n=n;

        for(int i=0;i<=n;i++)G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,int cap){  //建边

        edges.push_back((Edge){from,to,cap,0});

        edges.push_back((Edge){to,from,0,0});

        m=edges.size();

        G[from].push_back(m-2);

        G[to].push_back(m-1);

    }

    bool BFS()

    {

        Del(vis,0);

        queue<int> q;

        q.push(s);

        d[s]=0;

        vis[s]=1;

        while(!q.empty())

        {

            int x=q.front();q.pop();

            for(int i=0;i<G[x].size();i++)

            {

                Edge &e =edges[G[x][i]];

                if(!vis[e.to] && e.cap>e.flow)

                {

                    vis[e.to]=1;

                    d[e.to]=d[x]+1;

                    q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int DFS(int x,int a)

    {

        if(x==t || a==0)

            return a;

        int flow=0,f;

        for(int& i=cur[x];i<G[x].size();i++)

        {

            Edge & e = edges[G[x][i]];

            if(d[x]+1 == d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0)

            {

                e.flow+=f;

                edges[G[x][i]^1].flow -= f;

                flow+=f;

                a-=f;

                if(a==0)

                    break;

            }

        }

        return flow;

    }

    int max_flow(int s,int t)

    {

        this->s=s;this->t=t;

        int flow=0;

        while(BFS())

        {

            Del(cur,0);

            flow+=DFS(s,INF);

        }

        return flow;

    }

};

Dinic solve;

int main()

{

    int n,m;

    while(~scanf("%d%d",&m,&n))

    {

        solve.init(n);

        for(int i=0; i<m; i++)

        {

            int x,y,z;

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

            solve.AddEdge(x,y,z);

        }

        printf("%d\n",solve.max_flow(1,n));  //出发点和结尾点

    }

    return 0;

}