题目描述 Description
给出一张n*n(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。
输入描述 Input Description
第一行为n，m（表示有m个删除的格子）
第二行到m+1行为x,y，分别表示删除格子所在的位置
x为第x行
y为第y列
输出描述 Output Description
一个数，即最大覆盖格数
样例输入 Sample Input
8 0
样例输出 Sample Output
32
数据范围及提示 Data Size & Hint
经典问题
/*
模板题
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define ll long long
using namespace std;
const int N = ;
struct edge{
int v;
int nxt;
}e[N*];
int head[N],cnt;
int n,m;
bool vis[][];
int chk[N],mch[N];
int read(){
int x=,f=;
char ch=getchar();
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
void ins(int u,int v){
cnt++;
e[cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
bool dfs(int u){
int to;
for(int i = head[u];i;i=e[i].nxt){
to = e[i].v;
if(!chk[to]){
chk[to] = true;
if(mch[to] == - || dfs(mch[to])){
mch[to] = u;
mch[u] = to;
return true;
}
}
}
return false;
}
void hun(){
int ans = ,lm = n*n;
memset(mch,-,sizeof(mch));
for(int i = ;i <= lm;i++){
if(mch[i] == -){
memset(chk,,sizeof(chk));
if(dfs(i)) ++ans;
}
}
cout<<ans;
}
int main(){
n = read();
m = read();
int x,y;
for(int i = ;i <= m;i++){
y = read();
x = read();
vis[y][x] = true;
}
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
if(vis[i][j]) continue;
if(j < n && !vis[i][j+]){
ins((i-)*n+j,(i-)*n+j+);
ins((i-)*n+j+,(i-)*n+j);
}
if(i < n && !vis[i+][j]){
ins((i-)*n+j,i*n+j);
ins(i*n+j,(i-)*n+j);
}
}
}
hun();
return ;
}