[Acwing] 372. 棋盘覆盖 二分图最大匹配+转换问题

前言

传送门 :

思路

首先 状压是不行了,我们考虑换个思维

如果我们将这个棋盘 进行黑白染色,奇数点为黑色,偶数点为白色

那么一个骨牌的放置就相当于在 黑白里面连了一个边 , 必然只能压倒一个 黑 和 白

(满足了 两个集合,单个集合之间不存在边 也就是 二分图 )

然后继续分析 , 不让骨牌重叠就是 不让两条边存在重复点

放最多的骨牌 就是 找对多的边

因此问题正好转换为 二分图最大匹配

code

const int N = 110;
pii match[N][N];
int n,m;

bool g[N][N],st[N][N];
int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};

bool find(int x,int y){
	for(int i = 0 ; i n) continue;
		if(!b || b>n) continue;
		if(g[a][b]) continue;
		if(st[a][b]) continue;
		
		st[a][b]  = 1;
		auto t = match[a][b];
		if(t.x ==-1 ||find(t.x,t.y)){
			match[a][b] = {x,y};
			return true;
		}
		
	}
	return false;
}

void solve(){
	int res =0  ;
	
	cin>>n>>m;
	for(int i=1;i>a>>b;
		g[a][b] = 1;
	}
	
	memset(match,-1,sizeof match);
	
	for(int i=1;i