网络流最大流模板

int fir[N],sz=1,to[N],flow[N],dl[N],deep[N], n,m;
void add1(int x,int y,int z){
    nxt[++sz]=fir[x];to[sz]=y;
    fir[x]=sz;flow[sz]=z;
}
void add(int x,int y,int z){
    add1(x,y,z),add1(y,x,0);
}
bool bfs(int S,int T){
    memset(deep,0,(tot+2)<<2);
    deep[S]=1;dl[1]=S;int head=0,tail=1;
    while(head!=tail){
        int v=dl[++head];
        for(int u=fir[v];u;u=nxt[u]){
            if(flow[u]&&!deep[to[u]]){
                deep[to[u]]=deep[v]+1;
                dl[++tail]=to[u];
            }
        }
    }
    return deep[T];
}
int aim;
int dfs(int now,int fl){
    if(now==aim)return fl;
    int f=0;
    for(int u=fir[now];u&&fl;u=nxt[u]){
        if(flow[u]&&deep[to[u]]==deep[now]+1){
            int x=dfs(to[u],min(fl,flow[u]));
            flow[u]-=x;flow[u^1]+=x;fl-=x;f+=x;
        }
    }
    if(!f)deep[now]=-2;
    return f;
}
int maxflow(int S,int T){
    aim=T;int ret=0;
    while(bfs(S,T)){
        ret+=dfs(S,1<<30);
    }
    return ret;
}

发表于 2019-09-17 20:54:14 in 笔记