题意
$n \times n$ 的棋盘上,有些方格禁止放置,问最多能放多少个 $1 \times 2$ 骨牌
分析
类似 AcWing 291. 蒙德里安的梦想,但数据范围较大,状压复杂度太高
把格子看成点,相邻格如果能放卡片,则连一条无向边。问题等价于最多能取多少条边,使得它们不含公共点,即最大匹配
判断图是否为二分图,否则不能用匈牙利算法。为方格染色,只染行号加列号等于奇数的方格。可以发现,所有边的顶点一端被染色,另一端未染色,因此是二分图
匈牙利算法只需从左部向右部枚举,可把行号加列号等于奇数的一端当作左部
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
pair<int, int> match[N][N];
bool g[N][N], st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool find(int x, int y) {
for (int i = 3; ~i; i --) {
int a = x + dx[i], b = y + dy[i];
if (!a || a > n || !b || b > n) continue;
if (!g[a][b] && !st[a][b]) {
st[a][b] = 1;
auto& [tx, ty] = match[a][b];
if (!tx || find(tx, ty))
return tx = x, ty = y;
}
}
return 0;
}
int main() {
cin >> n >> m;
for (int a, b; m; m --)
cin >> a >> b, g[a][b] = 1;
int ans = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if (!g[i][j] && (i + j) & 1) {
memset(st, 0, sizeof st);
if (find(i, j)) ans ++;
}
cout << ans << endl;
return 0;
}