模板——网络流Dinic

Bertha 。 2021-11-01 13:24 331阅读 0赞

感谢这位大佬的博客：[https://www.cnblogs.com/SYCstudio/p/7260613.html][https_www.cnblogs.com_SYCstudio_p_7260613.html] 给予了我莫大的帮助!

主要说一下网络流的几个注意点：

1.和二分图匹配相似，无法继续增广的网络流即为最大流，但可能因为增广顺序，之前增广的边导致后面更多的边无法增广，所以要允许反悔，即增广之后连反向边

2.因为在增广时可能同一条边来回被增广很多次，所以可能会因为边权差距太大而被卡死，所以要dinic优化分层图查找

3.没有当前弧优化的Dinic是很慢的。。。就是用邻接表记录对于x节点已经“消耗”到哪一条边了

废话不多说，附上代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int N=2005;
    const int inf=(int)2e9;
    
    int n,m,s,t;
    int e,first[N],nxt[N],point[N],w[N],cur[N];
    void add(int x,int y,int z)
    {
        e++;
        point[e]=y;
        nxt[e]=first[x];
        first[x]=e;
        w[e]=z;
    }
    
    void add_edge(int x,int y,int z)
    {
        add(x,y,z);
        add(y,x,0);
    }
    
    void init()
    {
        e=-1;
        memset(first,-1,sizeof(first));
        memset(nxt,-1,sizeof(nxt));
    }
    
    int depth[N];
    bool bfs()
    {
        memset(depth,0,sizeof(depth));
        queue<int> q;
        while(!q.empty()) q.pop();
        q.push(s); depth[s]=1;
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            for(int i=first[u];i!=-1;i=nxt[i])
            {
                int v=point[i];
                if(depth[v]||!w[i]) continue;
                depth[v]=depth[u]+1;
                q.push(v);
            }
        }
        if(depth[t]>0) return 1;
        return 0;
    }
    
    int dfs(int u,int flows)
    {
        if(u==t) return flows;
        for(int& i=cur[u];i!=-1;i=nxt[i])
        {
            int v=point[i];
            if(w[i]!=0&&depth[v]==depth[u]+1)
            {
                int d=dfs(v,min(w[i],flows));
                if(d)
                {
                    w[i]-=d;
                    w[i^1]+=d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    int Dinic()
    {
        int ans=0;
        while(bfs())
        {
            for(int i=1;i<=n;i++) cur[i]=first[i];
            while(int d=dfs(s,inf))
            {
                ans+=d;
            }
        }
        return ans;
    }
    
    int main() {
        int T; cin>>T;
        for(int iii=1;iii<=T;iii++)
        {
            init();
            scanf("%d%d",&n,&m);
            s=1; t=n;
            for(int i=1;i<=m;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                add_edge(x,y,z);
            }
            printf("Case %d: %d\n",iii,Dinic());
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11173128.html

[https_www.cnblogs.com_SYCstudio_p_7260613.html]: https://www.cnblogs.com/SYCstudio/p/7260613.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/43f109047c3644ab9811a01483193cf0.png