最大流

dinic算法

struct node{
    int Next,y,v;
}Pth[880005];
int tot=1,head[20005];
inline void add(int x,int y,int v){
    Pth[++tot]={head[x],y,v};head[x]=tot;
    Pth[++tot]={head[y],x,0};head[y]=tot;
}
int d[20005],S,T,INF=0x3f3f3f3f;
int qu[60005];
bool bfs(){
    memset(d,0,sizeof d);
    int l=0,r=0;
    qu[++r]=S; d[S]=1;
    while (l<r){
        int x=qu[++l];
        for (int i=head[x];i;i=Pth[i].Next){
            int y=Pth[i].y;
            if (!d[y] && Pth[i].v){
                d[y]=d[x]+1;
                qu[++r]=y;
                if (y==T) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if (x==T) return flow;
    int rest=flow,k;
    for (int i=head[x];i&&rest;i=Pth[i].Next){
        int y=Pth[i].y;
        if (Pth[i].v && d[y]==d[x]+1){
            k=dinic(y,min(rest,Pth[i].v));
            if (!k) d[y]=0;
            Pth[i].v-=k;
            Pth[i^1].v+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
ll solve(int s,int t){
    ll flow,maxflow=0;
    S=s,T=t;
    while (bfs()){
        while (flow=dinic(s,INF)) maxflow+=flow;
    }
    return maxflow;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/%E7%BD%91%E7%BB%9C%E6%B5%81/