【洛谷5222】Game(费用流)

点此看题面

  • 一张\(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;//能支付代价与放每种数量棋子最小代价比较
}
上一篇:Libgdx New 3D API 教程之 -- 使用Libgdx加载模型


下一篇:自定义PopupWindow 怎么设置PopupWindow的宽度充满全屏宽度