一道网络流题目和其相关套路：ZR2627紫罗兰

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132296366

http://zhengruioi.com/problem/2627

Trick1：二分套网络流

首先可以对原图建模

中间拆点是为了两对棋子走到同一个格子上

然后我们发现每条边除了容量还有一个边权， 而我们的目标是求出 每一个流量下的最小边权

对于网络流中出现边权最值问题，可以进行二分。二分过程时枚举最值，然后 保留可行边 ，来跑网络流

Trick2：动态加边维护增广路

对于能够在网络流上通过上述二分的问题，都可以通过这种方法。

考虑网络流找的是什么？增广路！

动态加入每条边，每次加完跑一遍增广路即可

Trick3：基于增广路数量的bfs

回到原题，发现增广路数量 最多为 $n^2$ 个 ，所以让它最多增广 $n^2$ 次

维护一个 $vis$ 数组，表示一个点在增广 $i$ 次后是否能在残量网络上到达。加入一条边 $u\to v$ ，如果 $vis_u=1,vis_v=0$ ，那么就可以让 $vis_v=1$ ，并按照此方法bfs出去。 如果此时到达了汇点，说明当前残量网络出现了一条增广路。 此时直接从汇点EK即可。 注意在EK中还要维护反悔边！这样才能保证正确性。

EK的过程：

void EK() {
	int x=T; 
	while(x!=S) {
		G[x][pre[x]]=1; G[pre[x]][x]=0; 
		x=pre[x];  
	}
}

因此要在bfs过程中维护一个 $pre$

Trick4：bitset维护bfs过程

令每个点的出边集合为 $G_u$ ，那么bfs中有用的点 $v$ 为 G[u]&(~vis) ，bitset维护。