题意:给定一个\(N\)行\(N\)列的棋盘，已知某些格子禁止放置.求最多能往棋盘上放多少块的长度为\(2\)、宽度为\(1\)的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠.\(N<=100.\)
分析:二分图的难点往往是分析如何建图,即如何根据题意,挖掘性质,构建出一个二分图.
二分图匹配模型的两个要素:
"\(0\)要素":节点分成两个独立的集合,每个集合内部\(0\)条边.
"\(1\)要素":每个节点只能与\(1\)条匹配边相连.
本题中,我们把棋盘黑白染色,行号加列号为偶数:白色,否则黑色,那么格子分成了两个集合,这样染色保证了两个相同颜色的格子不可能会被同一个骨牌覆盖,符合"0要素".
一个格子(节点),最多会被一个骨牌覆盖到,符合"1要素".
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int M=50005;//调了半个小时,原来是数组开小了
int n,m,tot1,ans;
int a[M],bj[M],visit[M],match[M];
int tot,head[M],nxt[M<<1],to[M<<1];
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
nxt[++tot]=head[b];head[b]=tot;to[tot]=a;
}
inline bool dfs(int x){
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!visit[y]){
visit[y]=1;
if(!match[y]||dfs(match[y])){
match[y]=x;return true;
}
}
}
return false;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;++i){
int x=read(),y=read();
bj[(x-1)*n+y]=1;//标记不能放置的格子
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
int num=(i-1)*n+j;
if(bj[num])continue;
if((i+j)%2==0){//只找到左半部分的节点:白色格子
a[++tot1]=num;
if(num-n>=1){//分类讨论:向周围4个黑色格子连双向边
if(!bj[num-n])add(num,num-n);
}
if(num-1>=1){
if((!bj[num-1])&&(num%n!=1))add(num,num-1);
}
if(num+1<=n*n){
if((!bj[num+1])&&(num%n!=0))add(num,num+1);
}
if(num+n<=n*n){
if(!bj[num+n])add(num,num+n);
}
}
}
for(int i=1;i<=tot1;++i){//从每个白色格子开始跑增广路
memset(visit,0,sizeof(visit));
if(dfs(a[i]))++ans;
}
printf("%d\n",ans);
return 0;
}