速通网络流的代价就是忘的巨快

最大流

理论：

\(\text{bfs}\) 找 \(S\) 到每个点的经过最少边的路径，并对残量网络分层，根据层次反复做 \(\text{dfs}\) 每次找到一条增广路并更新

对于每一条从 \(x\) 出发并处理完毕的边都不需要重复只用，用 \(\text{cur[x]}\) 表示上次处理 \(x\) 时遍历的最后一条边(\(x\) 的当前弧)，每次 \(\text{bfs}\) 后都应将 \(\text{cur}\) 初始化为 \(\text{head}\)

尤其在稠密图中效果显著

namespace Webflow{
	inline int bfs(int st,int ed){//源点到所有点的最短路
		for(rei i=0;i<=n;++i) cur[i]=head[i],dis[i]=0;
		he=1,ta=0; dis[st]=1,que[++ta]=st;
		while(he<=ta){
			rei x=que[he++];
			for(rei i=head[x],y;i;i=Next[i]){
				if(flow[i] && !dis[ y=ver[i] ]){
					dis[y]=dis[x]+1; que[++ta]=y;
					if(y==ed) return 1;
				}
			}
		}
		return 0;
	}
	inline int dfs(int x,int left_flow){//left_flow是剩下的可用流量
		if(!left_flow || x==T) return left_flow;//没有流量或到达终点
		rei tmp=0;
		for(rei i=cur[x],y,f;i;i=Next[i]){
			cur[x]=i;
			if(dis[ y=ver[i] ]==dis[x]+1 && (f=dfs(y,min(left_flow-tmp,flow[i])))){
				//边权为0则不满足增广路性质，或者无法到达汇点，f值都为0
				flow[i]-=f; flow[i^1]+=f;
				tmp+=f;//终点已经从x获得了多少流
				if(!(left_flow-tmp)) break;
			}
		}
		return tmp;
	}
	inline void Dinic(int S,int T){ while(bfs(S,T)) maxflow+=dfs(S,INF);}
}