最大流dinci模板

矫情吗；* 2022-08-10 14:44 156阅读 0赞

我们知道，增广路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;
    }