AcWing 棋盘覆盖
Description
给定一个N行N列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
Input
第一行包含两个整数N和t，其中t为禁止放置的格子的数量。
接下来t行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
Output
- 输出一个整数，表示结果。
Sample Input
8 0
Sample Output
32
题解：
- 二分图匹配。
- 二分图匹配讲究"01原则"。
- "0"：能将对象抽象成两个部分，每个部分内部没有连边。
- "1"：每个部分里的点只能与对面的点连一条边。
- 注：一对多的情况也是要利用拆点转换成一对一的模型。
- 那么看看这一题。
- 一个矩形占了两个格子，那么我可以看成这个矩形就是一条边，连接了其所占的两个格子。那么，二分图模型中的"1"原则我们就满足了。那么怎么样将格子图分为两个部分呢？用按照奇偶性分类的常用技巧将格子分为两大部分。这样，每个部分的格子之间没有连边，满足了"0"原则。最后，求出最大匹配数即可。
#include#include #include #define N 105#define M 1000005using namespace std;struct E {int next, to;} e[M];int n, m, num, ans;int h[N * N], mat[N * N];int dx[5] = {0, -1, 1, 0, 0};int dy[5] = {0, 0, 0, -1, 1};bool vis[N * N];bool tag[N][N];void add(int u, int v){ e[++num].next = h[u]; e[num].to = v; h[u] = num;}int cal(int x, int y) {return (x - 1) * n + y;}bool dfs(int x){ for(int i = h[x]; i != 0; i = e[i].next) if(!vis[e[i].to]) { vis[e[i].to] = 1; if(!mat[e[i].to] || dfs(mat[e[i].to])) { mat[e[i].to] = x; return 1; } } return 0;}int main(){ cin >> n >> m; for(int i = 1; i <= m; i++) { int x, y; cin >> x >> y; tag[x][y] = 1; } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= 4; k++) { int x = i, y = j; int xx = x + dx[k], yy = y + dy[k]; if(xx < 1 || xx > n || yy < 1 || yy > n) continue; if(tag[x][y] || tag[xx][yy]) continue; add(cal(x, y), cal(xx, yy)); add(cal(xx, yy), cal(x, y)); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if((i + j) % 2) { memset(vis, 0, sizeof(vis)); if(dfs(cal(i, j))) ans++; } cout << ans; return 0;}