最大流模板
需要注意的是要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;