Luogu题面

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10001],A[101][101],fl,fr,ans,id;
bool f[10001];
int head[10001],last[10001];
struct node {
	int to,next;
} e[100009];
void add(int u,int v) {
	++id;
	if(head[u]==0) head[u]=id;
	else e[last[u]].next=id;
	last[u]=id,e[id].to=v;
}
bool dfs(int x) {
	for(int i = head[x]; i != 0; i = e[i].next) {
		if(!f[e[i].to]) {
			f[e[i].to]=1;
			if(a[e[i].to]==0||dfs(a[e[i].to])==1) {
				a[e[i].to]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	scanf("%d%d",&n,&k);
	for(int i = 1; i <= k; i++) {
		scanf("%d%d",&fl,&fr);
		A[fl][fr]=1;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j < n; j++) {
			if(A[i][j]||A[i][j+1]) continue;
 			add(i*n+j-n,i*n+j+1-n);
 			add(i*n+j+1-n,i*n+j-n);
		}
	}
	for(int i = 1; i < n; i++) {
		for(int j = 1; j <= n; j++){
			if(A[i][j]||A[i+1][j]) continue;
			add(i*n+j-n,i*n+j);
			add(i*n+j,i*n+j-n);
		}
	}
	for(int i = 1; i <= n*n; i+=2) {
		if(A[(i-1)/n+1][i%n]) continue;
		for(int j = 1; j <= n*n; j++) f[j]=0;
		ans+=dfs(i);
	}
	printf("%d\n",ans);
	return 0;
}