牛客图论 (第一章)

F 棋盘覆盖

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 105 , M = N * N * 4 , ID = N * N + N;

int n,m;
int head[ID],ver[M],nxt[M],tot;
bool ban[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int match[ID];
bool v[ID];

void add(int x,int y) {
	ver[++tot] = y , nxt[tot] = head[x] , head[x] = tot;
}
int get(int x,int y) {
	return x * N + y;
}
bool dfs(int x) {
	
	for(int i = head[x] ; i ; i = nxt[i]) {
		int y = ver[i];
		if(v[y]) continue;
		v[y] = true;
		if (!match[y] || dfs(match[y])) {
			match[y] = x;
			return true;	
		}
	}
	
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
	cin >> n >> m;
	
	while (m--) {
		int x,y;
		cin >> x >> y;
		ban[x][y] = true;
	}
	
	for(int x1 = 1 ; x1 <= n ; ++x1)
		for(int y1 = 1 ; y1 <= n; ++y1) {
			if(ban[x1][y1] || ( (x1 + y1) & 1) ) continue;
			for(int k = 0 ; k < 4 ; ++k) {
				int x2 = x1 + dx[k] , y2 = y1 + dy[k];
				if(x2 < 1 || x2 > n || y2 < 1 || y2 > n || ban[x2][y2]) continue;
				add(get(x1 , y1) , get(x2 , y2));
			}
		}
	
	int ans = 0;
	for(int x = 1 ; x <= n ; ++x)
		for(int y = 1 ; y <= n ; ++y){
			if(ban[x][y] || ( (x + y) & 1) ) continue;
			memset(v , 0 , sizeof v);
			if(dfs(get(x , y))) ++ans;
		}
		
	cout << ans << '\n';
	
	return 0;
}