输入样例：
8 0
输出样例：
32解析：
n为100，状压肯定爆。文章来源：https://www.toymoban.com/news/detail-625768.html
将每个骨牌看成二分图的一个匹配，即查找二分图的一个最大匹配，匈牙利算法。文章来源地址https://www.toymoban.com/news/detail-625768.html
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,t,vis[N][N],g[N][N];
pair<int,int> match[N][N];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int check(int x,int y){
return x>0&&y>0&&x<=n&&y<=n;
}
bool find(int x,int y){
for(int i=0;i<4;i++){
int dx=x+dir[i][0];
int dy=y+dir[i][1];
if(!vis[dx][dy]&&check(dx,dy)&&!g[dx][dy]){
vis[dx][dy]=1;
pair<int,int>p=match[dx][dy];
if(p.first==0||find(p.first,p.second)){
match[dx][dy]={x,y};
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d",&n,&t);
for(int i=0;i<t;i++){
int a,b;
scanf("%d%d",&a,&b);
g[a][b]=1;
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]) continue;
if((i+j)%2){
memset(vis,0,sizeof vis);
if(find(i,j)) res++;
}
}
}
cout<<res;
return 0;
}到了这里，关于AcWing 372. 棋盘覆盖（二分图&&匈牙利算法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
