【线性规划与网络流24题#24】骑士共存

本文主要是介绍【线性规划与网络流24题#24】骑士共存，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述
在一个n×n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。
在这里插入图片描述
对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

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

输出格式
一个整数，计算出的共存骑士数

样例输入
3 2
1 1
3 3

样例输出
5

思路
讲每一个点与他可以攻击的点连边
跑一次匹配
减去结果除以2就是答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int cross=211;
ll head[cross*cross],tot=0,nx[cross*cross*8],to[cross*cross*8];
void linkit(int u,int v)
{to[tot]=v;nx[tot]=head[u];head[u]=tot++;
}
const int b[8][2]={1,2, -1,2, 1,-2, -1,-2 ,2,1, -2,1, 2,-1, -2,-1};
int link[cross*cross],point[cross][cross],cnt=0;
bool bad[cross][cross],road[cross*cross];
bool findit(int x){for(int i=head[x];i!=-1;i=nx[i]){int y=to[i];if(!road[y]){road[y]=true;if(!link[y]||findit(link[y])){link[y]=x;return true;}}}return false;
}
int main(){memset(head,-1,sizeof(head));int n,m;scanf("%d%d",&n,&m);for(int i = 1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);bad[x][y]=true;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!bad[i][j])point[i][j]=++cnt;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(bad[i][j])continue;for(int k=0;k<8;k++){int xx=i+b[k][0];int yy=j+b[k][1];if(xx<=0||yy<=0||xx>n||yy>n)continue;if(bad[xx][yy])continue;if((i+j)&1)linkit(point[i][j],point[xx][yy]);elselinkit(point[xx][yy],point[i][j]);}}int ans=cnt;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(bad[i][j])continue;if((i+j)&1){memset(road,false,sizeof(road));if(findit(point[i][j]))ans--;} }printf("%d",ans);  return 0;
}