Description：

网格图上有 $T$ 个障碍。一开始选择棋盘第一列的一些格子放上一枚棋子。然后每次选择一枚棋子上下移动或者把所有棋子向右移动，如果下一个位置是坏的就不动，每一次给顶 $k_i$ ，询问最多能在第一列上放多少枚棋子使得经过若干次操作后你能将所有棋子移动到最后一列，且所有棋子加起来最多执行 $k_i$ 次 $1$ 操作。

$1\leqslant n\leqslant 50,1\leqslant m\leqslant 10^6$

Solution：

因为两个棋子在同一行最后分开和一开始就分开本质相同，那么我们可以用网络流，左右连容量为 $1$ 费用为 $0$ 的边，上下连容量为 $\infty$ 费用为 $1$ 的边跑网络流即可，因为 $EK$ 每次只增广一条路径，所以可以预处理所有答案，有几个优化：一是可以省去很多没有障碍的列，只保留有障碍的和前面那一列，而是边权都是 $0,-1,1$ ，可以用 $SPFA$ 双端队列优化。

Code：

没有代码