网络流的板子-最大流(dinic)

shadowice1984 · 2018-04-04 20:18:06 · 个人记录

这里是shadowice1984自用的板子……

由于是给自己写的板子所以不会有太详细的解释……

tips:cnt=1,用板子的时候染色编号非常重要

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=4010;const int M=4*1e6+10;
int v[M];int x[M];int c[M];int al[N];int ct=1;queue <int> q;int d[N];
int s;int t;int ctt;
inline void add(int u,int V,int cot)
{
    v[++ct]=V;x[ct]=al[u];c[ct]=cot;al[u]=ct;
    v[++ct]=u,x[ct]=al[V];c[ct]=0;al[V]=ct;
}
inline bool bfs()
{
    for(int i=1;i<=ctt;i++){d[i]=0x3f3f3f3f;}
    for(d[s]=0,q.push(s);!q.empty();q.pop())
    {
        for(int nw=q.front(),i=al[nw];i;i=x[i])
        {
            if(d[v[i]]!=0x3f3f3f3f||c[i]==0){continue;}
            d[v[i]]=d[nw+1];q.push(v[i]);
        }
    }return d[t]!=0x3f3f3f3f;
}
inline int dfs(int u,int lim)
{
    if(u==t){return lim;}int f=0;
    for(int i=al[u];i&&lim;i=x[i])
    {
        if(d[v[i]]!=d[u]+1||c[i]==0){continue;}
        int de=dfs(v[i],min(lim,c[i]));
        c[i]-=de;c[i^1]+=de;lim-=de;f+=de;
    }d[u]=f?d[u]:0x3f3f3f3f;return f;
}