- 一张(n imes m)的棋盘，其中有(k)个无法摆放棋子的障碍格。
- 一开始在第一列放上一些棋子，每次可以花费(1)点代价将某一棋子上移/下移一行，或是将所有棋子一起右移一列，要求把所有棋子一起移到最后一列。
- (q)次询问，每次给出能支付的最大代价，求一开始最多能放多少棋子。
- (nle50,mle10^6,kle10^3,qle10^5)
费用流
考虑最多只能放(n)个棋子，因此我们不妨求出放(i)个棋子最少需要支付的代价(ans_i)，每次询问与当前能支付的代价比较一下就能求出答案了。
所以我们使用费用流，每次多流一点流量，求出新增这一点流量所需的最小费用累加即可。
但暴力建图复杂度肯定炸飞，需要优化。
排除冗余列
发现如果第(i)列和第(i+1)列都没有障碍，我们肯定没必要在第(i)列执行任何操作——因为任何可以在第(i)列执行的操作都可以放在第(i+1)列执行。
因此我们只要保留有障碍的列及其前一列，那么(mle10^6)不过是个幌子。
缩点
首先要知道一个转化，将(x)个连续棋子一起上移一行，等价于将最下方的棋子上移(x)行。
也就是说，我们可以修改一下操作方式，认为可以花费(|i-j|)的代价把第(i)行的棋子移到第(j)行，要求(isim 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
",i);}return 0;//能支付代价与放每种数量棋子最小代价比较
}