给定一个 NNN 行 NNN 列的棋盘,已知某些格子禁止放置.
求最多能往棋盘上放多少块的长度为 222 ,宽度为 111 的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠.
第一行包含两个整数 NNN 和 ttt ,其中 ttt 为禁止放置的格子的数量.
0≤t≤1000 \le t \le 1000≤t≤100
咱自己也没搞明白这题是怎么 想到 二分图最大匹配的,所以以下只解释怎么把该题 转换 为二分图最大匹配问题.
这样的棋盘(黑色代表禁止放置的格子,为方便起见对所有格子标了序号)可以建出以下图:
这样以来这个问题就转换成为了 在选择的边不含公共点的前提下,最多能取多少条边 ,也就是 最大匹配 问题.
那么如何证明这个图是二分图呢?证明这个图是二分图就等同于证明这个图可以被二染色.
这个图当然可以被二染色,如下:
只要按照这种规则,所有 n×mn \times mn×m 的矩阵都可以被二染色.且所有奇数行奇数列或偶数行偶数列的格子为一种颜色,所有奇数行偶数列或偶数行奇数列的格子为另一种颜色.
自此以来,这个问题就被转换为了二分图求最大匹配问题,可以直接用匈牙利算法求解.