poj 2446
题意：给出一个网格图，有$k$个格子是空洞，然后用$1 \times 2$的矩形，对所有非空洞的格子进行覆盖，问是否可以全部覆盖。
考虑将图黑白染色，即相邻的格子颜色不同(黑白相间)。本题就是相当于将白格和黑格进行匹配，连边二分图，然后求出最大匹配即可。但是最大匹配后可能还会有$1 \times 1$的小方块不在匹配中，要验证答案。
对于一个点$(x,y)$，如果$x,y$是奇数，则他是一种颜色；反之是另一种颜色。我们用这种方法来区分颜色。注意障碍物不要连边。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define pb push_back
using namespace std;
int m, n, k, map[40][40], vis[2000], cnt, lk[2000];
vector<int> G[2000];
inline int getID(int x, int y) {return (x - 1) * n + y;}
int hungary(int u) {
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (vis[v] != cnt) {
vis[v] = cnt;
if (!lk[v] || hungary(lk[v])) {
lk[v] = u;
return true;
}
}
}
return false;
}
void clean() {
ms(lk, 0), ms(map, 0), ms(vis, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i <= k; i++) scanf("%d%d", &x, &y), map[y][x] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (!map[i][j]) {
if (i - 1 > 0 && !map[i - 1][j]) {
if ((i + j) % 2) {
G[getID(i - 1, j)].pb(getID(i, j));
} else {
G[getID(i, j)].pb(getID(i - 1, j));
}
}
if (j - 1 > 0 && !map[i][j - 1]) {
if ((i + j) % 2) {
G[getID(i, j - 1)].pb(getID(i, j));
} else {
G[getID(i, j)].pb(getID(i, j - 1));
}
}
}
}
}
int ans = 0;
for (int i = 1; i <= getID(m, n); i++)
ans += hungary(cnt = i);
if (ans * 2 + k == m * n) printf("YES\n"); else printf("NO\n");
return 0;
}
int main() {
scanf("%d%d%d", &m, &n, &k), solve();
return 0;
}
/*
4 4 2
1 4
4 2
*/
