最大流模板

需要注意的是要ll就全ll,不然要出事。

struct Flow
{
    ll tot=1,hd[N],ne[M],to[M],lim[M];
    void Add(int x,int y,ll z)
    {
        ne[++tot]=hd[x];hd[x]=tot;to[tot]=y;lim[tot]=z;
        ne[++tot]=hd[y];hd[y]=tot;to[tot]=x;lim[tot]=0;
    }
    ll T,dis[N],cur[N];
    ll Dfs(ll x,ll res)
    {
        if(x==T)return res;
        ll flow=0;
        for(int i=cur[x];i&&res;i=ne[i])
        {
            cur[x]=i;ll w=min(res,(ll)lim[i]),y=to[i],z;
            if(dis[x]+1==dis[y]&&w)z=Dfs(y,w),flow+=z,res-=z,lim[i]-=z,lim[i^1]+=z;
        }
        if(!flow)dis[x]=-1;
        return flow;
    }
    ll Maxflow(int s,int t)
    {
        T=t;ll flow=0;
        while(1)
        {
            queue<int>q;q.push(s);memcpy(cur,hd,sizeof(hd));
            memset(dis,-1,sizeof(dis));dis[s]=0;
            while(!q.empty())
            {
                int x=q.front();q.pop();
                for(int i=hd[x];i;i=ne[i])if(dis[to[i]]==-1&&lim[i])
                    dis[to[i]]=dis[x]+1,q.push(to[i]);
            }
            if(dis[t]==-1)return flow;
            flow+=Dfs(s,1e18);
        }
    }
}G;