P3355 骑士共存问题

P3355 骑士共存问题

我还没学网络流所以先讲二分图的做法，讲述下思路怎么推出来的。

可以发现骑士可达的点的颜色总是与自己的颜色相反，放了这个骑士，周围可达的方格就不能放骑士，要求客房的最多骑士数量，发现这与二分图最大匹配是相同的，所以直接进行分点匹配。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=205;
const int M=20005;
int n,m;
int ok[N][N];//障碍 
int one,two;//奇偶点数
int g[N][N]; 
int xx[M],yy[M]; 
int lin[M];
int vis[M];
int dx[N]={1,1,-1,-1,2,2,-2,-2};
int dy[N]={2,-2,2,-2,1,-1,1,-1};
int check(int a){
	int k,q,x,y;
	for(int i=0;i<8;i++){
		x=xx[a]+dx[i];
		y=yy[a]+dy[i];
		k=g[x][y];
		if(x<1||y<1||x>n||y>n||vis[k]||ok[x][y]){//不合法 
			continue;
		}
		vis[k]=1;//遍历过 
		q=lin[k];//他的所属 
		lin[k]=a; //强制连接 
		if(!q||check(q)){//可以匹配到 
			return 1;
		} 
		lin[k]=q;//失配归位 
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		ok[x][y]=1; 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(ok[i][j]){//障碍 
				continue;
			}
			if((i+j)&1){//对奇偶性分点 
				g[i][j]=++one;	
				xx[one]=i;
				yy[one]=j;
			} 
			else{
				g[i][j]=++two;
			}
		}
	}
	int ans=n*n-m;//空位数 
	for(int i=1;i<=one;i++){
		if(check(i)){//匹配到了，少空格子 
			memset(vis,0,sizeof vis);
			ans--;
		}
	}
	cout<<ans;
    return 0;
}