首页 > 代码库 > 【BZOJ4930】棋盘 拆边费用流

【BZOJ4930】棋盘 拆边费用流

【BZOJ4930】棋盘

Description

给定一个n×n的棋盘,棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置(x,y),(u,v)能互相攻击当前仅
当满足以下两个条件:
1:x=u或y=v
2:对于(x,y)与(u,v)之间的所有位置,均不是障碍。
现在有q个询问,每个询问给定ki,要求从棋盘中选出ki个空位置来放棋子,问最少互相能攻击到的棋子对数是多少?

Input

第一行一个整数n。
接下来输入一个n×n的字符矩阵,一个位置若为.,则表示这是一个空位置,若为#,则为障碍。
第n+2行输入一个整数q代表询问个数。
接下来q行,每行一个整数k,代表要放的棋子个数。
n ≤ 50, q ≤ 10000, k ≤ 棋盘中空位置数量

Output

输出共q行,每行代表对应询问的最少的互相能攻击到的棋子对数。

Sample Input

4
..#.
####
..#.
..#.
1 7

Sample Output

2

题解:还是集训原题~

如果你做过了BZOJ4554游戏那道题,还做过了修车,那么这道题岂不是很水?

如果没有障碍,那么我们显然是将网格按照行和列拆分,然后每行向每列连边,然后搞一搞,不过有障碍怎么办呢?

我们如果一行中有a段连续的障碍,我们认为每段障碍都将这行切成了两段,那么一共被切成了a+1段。类似地,每列也都被切成了好几段。那么我们得到了一堆行和一堆列,现在我们想在它们之间连边。

先考虑每一段行,在这个行中放一个棋子,产生的冲突数为0,再放1枚,冲突数+1,再放1枚,冲突数+2。。。那么我们显然可以考虑拆边。就有了建图方法:

设第i个行(被切过的)为hi,第j个列为rj,那么:

1.S -> hi 连若干条边,其中第k条费用为k-1,容量为1。
2.对于网格中的非障碍点(i,j),hi -> rj 费用为0,容量为1。
3.rj -> T 连若干条边,其中第k条费用为k-1,容量为1。

由于考试的时候我比较怂,所以写的动态加边,好像没什么必要~

练完边,跑完费用流后,再一起处理询问就好啦~

#include <cstdio>#include <cstring>#include <iostream>#include <queue>#define P(A,B) ((A-1)*n+B)using namespace std;int n,m,S,T,cnt,sum,tot,mf,nx,ny;char str[60][60];int to[1000000],next[1000000],cost[1000000],flow[1000000],dis[10000],inq[10000],pe[10000],pv[10000],head[10000];int ans[10000],bx[60][60],by[60][60],lx[10000],ly[10000],ux[10000],uy[10000];queue<int> q;void add(int a,int b,int c,int d){	to[cnt]=b,cost[cnt]=c,flow[cnt]=d,next[cnt]=head[a],head[a]=cnt++;	to[cnt]=a,cost[cnt]=-c,flow[cnt]=0,next[cnt]=head[b],head[b]=cnt++;}int bfs(){	memset(dis,0x3f,sizeof(dis));	dis[S]=0,q.push(S);	int i,u;	while(!q.empty())	{		u=q.front(),q.pop(),inq[u]=0;		for(i=head[u];i!=-1;i=next[i])		{			if(dis[to[i]]>dis[u]+cost[i]&&flow[i])			{				dis[to[i]]=dis[u]+cost[i],pe[to[i]]=i,pv[to[i]]=u;				if(!inq[to[i]])	inq[to[i]]=1,q.push(to[i]);			}		}	}	return dis[T]<0x3f3f3f3f;}int main(){	//freopen("chess.in","r",stdin);	//freopen("chess.out","w",stdout);	scanf("%d",&n);	int i,j,a;	memset(head,-1,sizeof(head));	for(i=1;i<=n;i++)	scanf("%s",str[i]);	for(i=1;i<=n;i++)	{		for(j=1;j<=n;j++)		{			if(j==1||(str[i][j-2]==‘#‘&&str[i][j-1]==‘.‘))	nx++;			if(str[i][j-1]==‘.‘)	lx[nx]++,bx[i][j]=nx;		}	}	for(j=1;j<=n;j++)	{		for(i=1;i<=n;i++)		{			if(i==1||(str[i-1][j-1]==‘#‘&&str[i][j-1]==‘.‘))	ny++;			if(str[i][j-1]==‘.‘)	ly[ny]++,by[i][j]=ny,add(bx[i][j],by[i][j]+nx,0,1);		}	}	S=0,T=nx+ny+1;	for(i=1;i<=nx;i++)	add(S,i,0,1);	for(i=1;i<=ny;i++)	add(i+nx,T,0,1);	while(bfs())	{		int mf=1<<30;		for(i=T;i!=S;i=pv[i])		{			mf=min(mf,flow[pe[i]]);			if(i>nx&&i<T)				if(uy[i-nx]<ly[i-nx])	add(i,T,++uy[i-nx],1);			if(i<=nx&&i>S)				if(ux[i]<lx[i])	add(S,i,++ux[i],1);		}		tot+=mf*dis[T];		ans[sum+=mf]=tot;		for(i=T;i!=S;i=pv[i])	flow[pe[i]]-=mf,flow[pe[i]^1]+=mf;	}	scanf("%d",&m);	for(i=1;i<=m;i++)	{		scanf("%d",&a);		printf("%d\n",ans[a]);	}	return 0;}

【BZOJ4930】棋盘 拆边费用流