【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

题解：还是集训原题~

如果你做过了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】棋盘拆边费用流

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

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

【BZOJ4930】棋盘 拆边费用流