- 一张\(n\times m\)的棋盘，其中有\(k\)个无法摆放棋子的障碍格。
- 一开始在第一列放上一些棋子，每次可以花费\(1\)点代价将某一棋子上移/下移一行，或是将所有棋子一起右移一列，要求把所有棋子一起移到最后一列。
- \(q\)次询问，每次给出能支付的最大代价，求一开始最多能放多少棋子。
- \(n\le50,m\le10^6,k\le10^3,q\le10^5\)
费用流
考虑最多只能放\(n\)个棋子，因此我们不妨求出放\(i\)个棋子最少需要支付的代价\(ans_i\)，每次询问与当前能支付的代价比较一下就能求出答案了。
所以我们使用费用流，每次多流一点流量，求出新增这一点流量所需的最小费用累加即可。
但暴力建图复杂度肯定炸飞，需要优化。
排除冗余列
发现如果第\(i\)列和第\(i+1\)列都没有障碍，我们肯定没必要在第\(i\)列执行任何操作——因为任何可以在第\(i\)列执行的操作都可以放在第\(i+1\)列执行。
因此我们只要保留有障碍的列及其前一列，那么\(m\le10^6\)不过是个幌子。
缩点
首先要知道一个转化，将\(x\)个连续棋子一起上移一行，等价于将最下方的棋子上移\(x\)行。
也就是说，我们可以修改一下操作方式，认为可以花费\(|i-j|\)的代价把第\(i\)行的棋子移到第\(j\)行，要求\(i\sim j\)之间没有障碍格。
那么一个显然的结论就是如果下一个格子没有障碍，我们必然不会去移动这个棋子。
换言之，对于同行连续一段没有障碍的格子，一旦我们在某一时刻进入了这段中，就必然会一直走到碰到障碍结束。
因此，我们可以把同行连续一段没有障碍的格子缩成一点。
具体建图
我们把一个点拆成入点和出点并在中间连一条容量为\(1\)、费用为\(0\)的边，保证每一段只能走一个棋子。
超级源向第一列所有非障碍格对应点连一条容量为\(1\)、费用为\(0\)的边，最后一列所有非障碍格向超级汇连一条容量为\(1\)、费用为\(0\)的边。
第\(i\)行碰到障碍时，向下一列所有可能走到的格子对应点（假设在第\(j\)行）连一条容量为\(1\)、费用为\(|i-j|\)的边。
由于一个障碍只会使得产生一对新点，算上超级源汇，点数是\(2(n+k)+2\)。
由于我们只会在遇到障碍时向下一列最多\(n\)个点连边，算上每个点自己的入出点连边和超级源汇与首列末列之间的连边，边数是\((n+k)+2n+kn\)。
代码：\(O(nk^2)\)
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50
#define K 1000
#define INF (int)1e9
using namespace std;
int n,m,k,px[K+5],py[K+5],dc,dv[2*K+5],ct,w[N+5][2*K+5],id[N+5][2*K+5];
class MinCostMaxFlow
{
private:
#define PS (2*(N+K)+2)
#define ES ((N+K)+2*N+K*N)
#define s (2*ct+1)
#define t (2*ct+2)
#define E(x) ((((x)-1)^1)+1)
int ee,lnk[PS+5];struct edge {int to,nxt,F,C;}e[2*ES+5];
int lst[PS+5],IQ[PS+5],F[PS+5],C[PS+5];deque<int> q;I bool SPFA()
{
RI i,k;for(i=1;i<=t;++i) C[i]=INF;q.push_front(s),C[s]=0;
W(!q.empty()) for(i=lnk[k=q.front()],q.pop_front(),IQ[k]=0;i;i=e[i].nxt)
{
if(!e[i].F||C[k]+e[i].C>=C[e[i].to]) continue;C[e[i].to]=C[k]+e[lst[e[i].to]=i].C;
!IQ[e[i].to]&&((q.empty()||C[q.front()]<C[e[i].to])?q.push_back(e[i].to):q.push_front(e[i].to),IQ[e[i].to]=1);
}return C[t]^INF;
}
public:
I void Add(CI x,CI y,CI f,CI c)
{
e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].F=f,e[ee].C=c,
e[++ee].nxt=lnk[y],e[lnk[y]=ee].to=x,e[ee].F=0,e[ee].C=-c;
}
int ans[N+5];I void MCMF()
{
RI x,f=0,g=0;W(SPFA()) {ans[++f]=(g+=C[t]),x=t;W(x^s) --e[lst[x]].F,++e[E(lst[x])].F,x=e[E(lst[x])].to;}//累加每增一点流量增加的费用
}
}D;
int main()
{
for(i=1;i<=k;++i) scanf("%d%d",px+i,py+i),py[i]>1&&(dv[++dc]=py[i]-1),dv[++dc]=py[i];
for(sort(dv+1,dv+dc+1),dc=unique(dv+1,dv+dc+1)-dv-1,i=1;i<=k;++i) w[px[i]][lower_bound(dv+1,dv+dc+1,py[i])-dv]=1;//离散化，给障碍格打标记
for(i=1;i<=n;++i) for(j=1;j<=dc;++j) !w[i][j]&&(id[i][j]=id[i][j-1]?id[i][j-1]:++ct);//缩点，连续一段非障碍格给上相同标号
for(i=1;i<=ct;++i) D.Add(i,ct+i,1,0);//入点向出点连边限制流量
for(i=1;i<=n;++i) !w[i][1]&&(D.Add(s,id[i][1],1,0),0),!w[i][dc]&&(D.Add(ct+id[i][dc],t,1,0),0);//超级源向首列非障碍格，末列非障碍格向超级汇
RI x;for(i=1;i<=n;++i) for(j=1;j^dc;++j) if(!w[i][j]&&w[i][j+1])//碰到障碍时需要切换
{
for(x=i-1;x>=1&&!w[x][j];--x) !w[x][j+1]&&(D.Add(ct+id[i][j],id[x][j+1],1,i-x),0);//向上，要求中间无障碍，费用i-j
for(x=i+1;x<=n&&!w[x][j];++x) !w[x][j+1]&&(D.Add(ct+id[i][j],id[x][j+1],1,x-i),0);//向下，要求中间无障碍，费用j-i
}
for(i=1;i<=n+1;++i) D.ans[i]=INF;D.MCMF();//跑费用流预处理放i个棋子的最小代价
W(Qt--) {for(scanf("%d",&x),i=0;D.ans[i+1]<=x;++i);printf("%d\n",i);}return 0;//能支付代价与放每种数量棋子最小代价比较
}