## [$AcWing$ $372$. 棋盘覆盖](https://www.acwing.com/problem/content/374/) ### 一、题目描述 给定一个 $N$ 行 $N$ 列的棋盘,已知某些格子禁止放置。 求最多能往棋盘上放多少块长度为 $2$ 、宽度为 $1$ 的骨牌,骨牌的边界与格线重合(骨牌占用 $2$ 个格子),并且任意两张骨牌都不重叠。 **输入格式** 第一行包含两个整数 $N$ 和 $t$,其中 $t$ 为禁止放置的格子的数量。 接下来 $t$ 行每行包含两个整数 $x$ 和 $y$,表示位于第 $x$ 行第 $y$ 列的格子禁止放置,行列数从 $1$ 开始。 **输出格式** 输出一个整数,表示结果。 **数据范围** $1≤N≤100,0≤t≤100$ **输入样例**: ```cpp {.line-numbers} 8 0 ``` **输出样例**: ```cpp {.line-numbers} 32 ``` ### 二、二分图应用【匈牙利算法求最大匹配】 **前置知识** * [匈牙利算法模板记忆及注释](https://www.cnblogs.com/littlehb/p/15337865.html) ### 三、题目分析 这题乍一看是状压$DP$,但是题目数据范围是$100$比较大,所以要考虑别的思路,由于卡片只能放到相邻的两个格子当中,我们把每个格子看作一个点,相邻两个格子连出一条边,于是这个题就抽象成了最多选多少条边,所有选出的边之间没有公共点,这就是最大匹配问题。 就比如下面这个图,黑色区域是禁止放置的
经过匹配之后:
求最大匹配问题可以用匈牙利算法求解,但是用匈牙利算法前提需要图是二分图,所以我们需要判断一下是不是二分图。 一个$n*n$的矩阵,我们通过染色把黑色区域看作一个集合,白色区域看作一个集合。 两个集合当中每个点相邻的点的颜色都是不同的,通过染色法判定我们发现这就是一个二分图。而且黑色区域每个点坐标和为偶数,白色区域每个点坐标和为奇数,因此我们就可以用匈牙利算法进行求解最大匹配问题。
**实现步骤:** * 建图(标记禁止放置的点) * 对二分图中的白色区域集合进行匹配并且更新答案 * 输出最大匹配数 考虑一个格子$(i,j)$: * $i+j$为偶数:记为 **黑格子** * $i+j$为奇数:记为 **白格子** 如果这个白格子没有被禁止,那么就让它向周围没有被禁止的黑格子连有向边,表示: **如果选择这条边(在这两个格子上放骨牌)会对答案有$1$的贡献** 显然白格子周围都是黑格子,所以白格子之间不会有边.那么这就是一个 **二分图最大匹配的模型** ,跑一下就好了. **时间复杂度** 最多$O(n^2)$个点,$O(n^2)$条边,所以时间复杂度$O(n^4)$ ### $Code$ ```cpp {.line-numbers} #include using namespace std; const int N = 10010, M = 40010; int n, m; int dx[] = {-1, 0, 1, 0}; // 上右下左 int dy[] = {0, 1, 0, -1}; // 上右下左 int g[N]; //一维的转换后表示,如果手欠,想写成二维的,一定要注意不能写N,要写110,否则会SE,不要问我是怎么知道的! // 链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } // 匈牙利算法模板 int match[N], st[N]; int find(int u) { for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; if (st[v]) continue; st[v] = 1; if (match[v] == -1 || find(match[v])) { match[v] = u; return 1; } } return 0; } int main() { memset(h, -1, sizeof h); // 初始化链式前向星 memset(match, -1, sizeof match); // 初始化匈牙利算法的匹配标识数组 scanf("%d %d", &n, &m); while (m--) { int a, b; scanf("%d%d", &a, &b); // 因为要做坐标变换,需要下标从0开始,本题下标从1开始,采用减一大法 a--, b--; g[a * n + b] = 1; } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (g[i * n + j]) continue; // 出发点有障碍物不可以 if ((i + j) % 2 == 0) continue; // 出发点是黑色点不可以 for (int k = 0; k < 4; k++) { int tx = i + dx[k], ty = j + dy[k]; if (g[tx * n + ty]) continue; // 目标点有障碍物 if (tx < 0 || tx == n || ty < 0 || ty == n) continue; // 目标点出界 add(i * n + j, tx * n + ty); // 加边 } } int res = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if ((i + j) % 2 == 1) { memset(st, 0, sizeof st); res += find(i * n + j); } printf("%d\n", res); return 0; } ```