「TYVJ1035」棋盘覆盖

题目描述

给出一张 \(n\) (\(n< =100\))的国际象棋棋盘，其中被删除了一些点，问可以使用多少\(1*2\)的多米诺骨牌进行掩盖。

输入

第一行为\(n\)，\(m\)（表示有\(m\)个删除的格子） 第二行到\(m+1\)行为\(x,y\)，分别表示删除格子所在的位置 \(x\)为第\(x\)行 \(y\)为第\(y\)列

输出

一个数，即最大覆盖格数

solution

我们可以显然地发现每张多米诺骨牌是覆盖了一个黑色格子和一个白色格子的

然后由于每个格子只能由一张多米诺骨牌覆盖（也就是不能重叠）

所以每个黑色格子只能和一个白色格子同在一张多米诺骨牌下

因此，我们可以将这个问题转换为二分图模型：

左部点=黑点（横纵坐标之和为偶数）

右部点=白点（横纵坐标之和为奇数）

边=多米诺骨牌

即我们将每两个合法的格子连边，表示我们可以在这两个格子上放一张骨牌

合法：其中任意一个格子未被删除且这两个格子相邻

每个点最多只能连一条边

因此我们跑二分图最大匹配即可

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+2,M=1e4+2;
vector<int>G[M];
int lx[]={0,0,1,-1},ly[]={1,-1,0,0};//方向数组
int ans,f[N][N],vis[M],x,y,n,m,match[M];//f记录被禁的点，vis用于枚举各左部点时标记
void add(int x,int y){
	G[x].push_back(y);
}
int dfs(int x){//匈牙利算法板子
	for(int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if(vis[y]) continue;
		vis[y]=1;
		if(match[y]==-1||dfs(match[y])){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
bool check(int x,int y){
	if(x<=0||x>n||y<=0||y>n) return 0;
	if(f[x][y]) return 0;
	if(!((x+y)&1)) return 0;
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		f[x][y]=1;//记录被禁放的点
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(f[i][j]) continue;
			for(int k=0;k<4;k++){//四个方向上相邻的点
				int x=i+lx[k],y=j+ly[k];//为了方便处理将二维转成一维，重新编号
				if(!check(x,y)) continue;//判断是否合法 
				add((i-1)*n+j,(x-1)*n+y); //加边
			} 
		}
	}
	memset(match,-1,sizeof(match));
	for(int i=1;i<=n*n;i++){//因为每个点都按一维处理，因此从1扫到n*n
		memset(vis,0,sizeof(vis));//每次找都要清空一次标记数组
		if(dfs(i))ans++;//如果左右匹配成功边数+1
	}
	printf("%d",ans);
	return 0;
}

完结撒花❀

★,°:.☆(￣▽￣)/$:.°★ 。