洛谷 P3355 骑士共存问题

2017-01-04 08:19:54来源:CSDN作者:SenyeLicone人点击

题目描述

在一个 n*n个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入

对于给定的 n*n 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击

输入输出格式

输入格式:

第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m<n2),分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数,表示障碍的方格坐标。

输出格式:

将计算出的共存骑士数输出

输入输出样例

输入样例#1:
3 21 13 3
输出样例#1:
5









~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

割~

因为每个骑士放置后,因他而不能放置的位置必定与他颜色不同,所以建立源点汇点,从源点向所有黑点连边,从白点向汇点连边,然后把每个黑点向能阻碍的点连边,最后求割,即为最多能放的骑士数。


#include<cstdio>#include<cstring>#include<iostream>#include<queue>using namespace std;#define inf 999999999int n,m,x,y,fi[40002],ne[500001],w[500001],v[500001],cnt,tot,ans,dis[40002];int nx[9]={0,1,2,-1,-2,1,2,-1,-2},ny[9]={0,2,1,-2,-1,-2,-1,2,1},z;bool b[201][201];void add(int u,int vv,int val){	w[++cnt]=vv;v[cnt]=val;ne[cnt]=fi[u];fi[u]=cnt;	w[++cnt]=u;v[cnt]=0;ne[cnt]=fi[vv];fi[vv]=cnt;}bool bfs(){	queue<int> q;	memset(dis,-1,sizeof(dis));	q.push(0);dis[0]=0;	while(!q.empty())	{		int k=q.front();q.pop();		for(int i=fi[k];i;i=ne[i])		  if(v[i]>0 && dis[w[i]]<0)		  {		  	dis[w[i]]=dis[k]+1;		  	if(w[i]==tot) return 1;		  	q.push(w[i]);		  }	}	return 0;}int findd(int u,int vv){	if(u==tot) return vv;	int kkz,now=0;	for(int i=fi[u];i;i=ne[i])	  if(v[i]>0 && dis[w[i]]==dis[u]+1 && (kkz=findd(w[i],min(v[i],vv-now))))	  {	  	v[i]-=kkz;v[i^1]+=kkz;now+=kkz;	  	if(now==vv) return now;	  }	if(!now) dis[u]=-1;	return now;}int main(){	scanf("%d%d",&n,&m);cnt=1;tot=n*n+1;	for(int i=1;i<=m;i++)	{		scanf("%d%d",&x,&y);b[x][y]=1;	}	for(int i=1;i<=n;i++)	  for(int j=1;j<=n;j++)	    if(!b[i][j])	    {	    	int now=(i-1)*n+j;	    	if(!((i+j)%2))	    	{	    		add(0,now,1);		    	for(int k=1;k<=8;k++)		    	  if(!b[i+nx[k]][j+ny[k]] && (i+nx[k])>0 && (i+nx[k])<=n && (j+ny[k])>0 && (j+ny[k])<=n)		    	  {		    	  	int now1=(i+nx[k]-1)*n+j+ny[k];		    	  	add(now,now1,inf);				  }			}	    	else add(now,tot,1);		}	while(bfs()) ans+=findd(0,inf);	printf("%d/n",n*n-m-ans);	return 0;}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台