记录编号	586302	评测结果	AATAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	90
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	1.383 s
提交时间	2024-01-12 18:58:41	内存使用	3.05 MiB

#include <bits/stdc++.h> 
using namespace std;
//二分图做法 
const int N = 5e4+10,M = 5e5+10;
int n,m,ans;
inline int read(){
	int x=0,sign=0; char s=getchar();
	while(!isdigit(s))sign|=s=='-',s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=getchar();
	return sign?-x:x;
}
struct made{
    int ver,nx;
}e[M];
int hd[N],tot;
int match[N],v[N];
int lx[10] = {0,-2,-1,1,2,2,1,-1,-2},ly[10] = {0,1,2,2,1,-1,-2,-2,-1};
bool a[210][210];
void add(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
int id(int x,int y){
    return (x-1)*n+y;
}
bool f(int x,int y){
    if(!a[x][y] && x > 0 && y > 0 && x <= n && y <= n)return 1;
    return 0;
}
void build(int x,int y){
    if(a[x][y])return;
    for(int i = 1;i <= 8;i++)
        if(f(x+lx[i],y+ly[i]))add(id(x,y),id(x+lx[i],y+ly[i]));
}
bool dfs(int x,int u){
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(v[y] == u)continue;
        v[y] = u;
        if(!match[y] || dfs(match[y],u)){
            match[y] = x;
            return 1;
        }
    }
    return 0;
}
int main(){
    freopen("knight.in","r",stdin);
    freopen("knight.out","w",stdout);
    n = read(),m = read();
    for(int i = 1;i <= m;i++){
        int x,y;
        x = read(),y = read();
        a[x][y] = 1;
    }
    for(int i = 1;i <= n;i++)
        for(int j = (i&1)?2:1;j <= n;j+=2)build(i,j);
    for(int i = 1;i <= n;i++)
        for(int j = (i&1)?2:1;j <= n;j+=2)
            if(!a[i][j])if(dfs(id(i,j),id(i,j)))ans++;
    printf("%d\n",n*n-ans-m);
    
    return 0;
    
}