Knights

Description

We are given a chess-board of size n * n, from which some fields have been removed. The task is to determine the maximum number of knights that can be placed on the remaining fields of the board in such a way that none of them check each other.
　　一张大小为n*n的国际象棋棋盘，上面有一些格子被拿走了，棋盘规模n不超过200。马的攻击方向如下图，其中S处为马位置，标有X的点为该马的攻击点。

Fig.1: A knight placed on the field S checks fields marked with x.
Write a program, that:
reads the description of a chess-board with some fields removed, from the input file kni.in,
determines the maximum number of knights that can be placed on the chess-board in such a way that none of them check each other,
writes the result to the output file kni.out.
你的任务是确定在这个棋盘上放置尽可能多的马，并使他们不互相攻击。

Input

The first line of the input file kni.in contains two integers n and m, separated by a single space, 1＜=n＜=200, 0＜=m＜n2; n is the chess-board size and m is the number of removed fields. Each of the following m lines contains two integers: x and y, separated by a single space, 1＜=x,y＜=n – these are the coordinates of the removed fields. The coordinates of the upper left corner of the board are (1,1), and of the bottom right are (n,n). The removed fields are not repeated in the file.

Output

The output file kni.out should contain one integer (in the first and only line of the file). It should be the maximum number of knights that can be placed on the given chess-board without checking each other.

Sample Input

3 2

1 1

3 3

Sample Output

5

解题思路

建模一：
对于本题来说，相互攻击的位置肯定不能同时存在两个马。 如果我们把两个相互攻击的位置连一条边，从而构成一个图。那么相邻 的两个点不能同时选，也就是求最大独立集

最大独立集
定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。 方法：最大独立集=所有顶点数-最小顶点覆盖。 定理：U=V-M；V=顶点数，M=最大匹配数（最小覆盖数），U=最大独立集。

在上面这个图中最小顶点覆盖=3，即2,4,7构成最小顶点覆盖，则其他点6个构成最大独立集。且其他点不可能相连。假设其他点相连则这条边必定没有被2,4,7 覆盖，与2,4,7是最小顶点覆盖矛盾。因此其他点之间必定没有边。而2,4,7是最小顶点覆盖，所谓最小就是不能再小了，因此我们的独立集就是最大了。

建模二 ：
考虑对棋盘进行黑白染色。具体来说，设某个点的位置是i行j列， 那么当[(i+j)%2==0]时，该点为黑色，否则该点为白色。 一个很显然的性质，相互攻击的两个位置颜色一定不同。我们把黑点 放在左边，白点放在右边，那么这个图一定是二分图。 首先我们把点进行编号。设格子有n行m列，第i行j列的格子被编号为 (i-1)*m+j。而对于被拿走的格子，我们完全可以认为这些点不存在， 不做任何处理。

	for(long long i=1;i<=n;i++)
	 for(long long j=1;j<=n;j++)
	  if(a[i][j]==0&&(i+j)%2==0)//判断，一是判断是否被拿走，二是判断是否为黑格或白格
	   for(long long k=0;k<8;k++)//枚举8种情况
	   {
   
	   	long long x=i+dx[k],y=j+dy[k];
	    if(x>=1&&x<=n&&y>=1&&y<=n)//出界
		 if(a[x][y]==0)//判断
		  add((i-1)*n+j,(x-1)*n+y);//连边
	   }

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,x,y,tot,answer,head[100005],cover[100005],father[100005],a[10005][10005];
long long dx[8]={
   -1,-2,-2,-1,1,2,2,1};
long long dy[8]={
   -2,-1,1,2,-2,-1,1,2};
struct node
{
   
	long long to,next;
}b[10000005];
void add(long long x,long long y)//邻接表
{
   
	b[++tot]=(node){
   y,head[x]};
	head[x]=tot;
}
bool dfs(long long x)//dfs
{
   
	if(x==0)return true;//特判
	for(long long i=head[x];i;i=b[i].next)//枚举边
	 if(cover[b[i].to]==0)//判断
	 {
   
	 	cover[b[i].to]=1;//标记
	 	long long sum=father[b[i].to];
		father[b[i].to]=x;
	 	if(sum==0||dfs(sum))return true;
	 	father[b[i].to]=sum;//回溯
	 }
	return false;//返回
}
int main()
{
   
	scanf("%lld%lld",&n,&m);//输入
	for(long long i=1;i<=m;i++)
	{
   
		scanf("%lld%lld",&x,&y);
		a[x][y]=1;
	}
	for(long long i=1;i<=n;i++)
	 for(long long j=1;j<=n;j++)
	  if(a[i][j]==0&&(i+j)%2==0)//判断，一是判断是否被拿走，二是判断是否为黑格或白格
	   for(long long k=0;k<8;k++)//枚举8种情况
	   {
   
	   	long long x=i+dx[k],y=j+dy[k];
	    if(x>=1&&x<=n&&y>=1&&y<=n)//出界
		 if(a[x][y]==0)//判断
		  add((i-1)*n+j,(x-1)*n+y);//连边
	   }
	for(long long i=1;i<=n*n;i++)
	{
   
		memset(cover,0,sizeof(cover));
		dfs(i);
	}
	for(long long i=1;i<=n*n;i++)
	 if(father[i]!=0)answer++;
	printf("%lld",n*n-m-answer);//顶点数-拿去的格子-最大匹配
	return 0; 
}

谢谢