题目
给定一个 行 列的棋盘,已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为 、宽度为 的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。
输入格式
第一行包含两个整数 和 ,其中 为禁止放置的格子的数量。
接下来 行每行包含两个整数 和 ,表示位于第 行第 列的格子禁止放置,行列数从 开始。
输出格式
输出一个整数,表示结果。
数据范围
,
输入样例:
8 0
输出样例:
32
解题
方法一:二分图最大匹配 匈牙利算法
思路
咱自己也没搞明白这题是怎么 想到 二分图最大匹配的,所以以下只解释怎么把该题 转换 为二分图最大匹配问题。
首先把所有格子看成点,然后对相邻的两个格子(可以放骨牌)连上一条边,例如:
这样的棋盘(黑色代表禁止放置的格子,为方便起见对所有格子标了序号)可以建出以下图:
这样以来这个问题就转换成为了 在选择的边不含公共点的前提下,最多能取多少条边 ,也就是 最大匹配 问题。
那么如何证明这个图是二分图呢?证明这个图是二分图就等同于证明这个图可以被二染色。
这个图当然可以被二染色,如下:
只要按照这种规则,所有 的矩阵都可以被二染色。且所有奇数行奇数列或偶数行偶数列的格子为一种颜色,所有奇数行偶数列或偶数行奇数列的格子为另一种颜色。
自此以来,这个问题就被转换为了二分图求最大匹配问题,可以直接用匈牙利算法求解。
代码
import java.util.*;
import java.io.*;
public class Main {
static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static int n, t;
static boolean[][] g;
static int N, M;
static int[] h, e, ne;
static int idx;
static int[] matchs;
static boolean[] vis;
static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// 原封不动的匈牙利算法求最大匹配
static boolean find(int u) {
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (!vis[v]) {
vis[v] = true;
if (matchs[v] == 0 || find(matchs[v])) {
matchs[v] = u;
return true;
}
}
}
return false;
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
n = in.nextInt();
t = in.nextInt();
g = new boolean[n + 1][n + 1];
while (t-- > 0) {
int x = in.nextInt(), y = in.nextInt();
g[x][y] = true;
}
// 格子最多N个 同一种颜色的格子最多N/2个 它们最大有机会向4个方向连边
// 所以最大可能有M=N/2*4条边 当然M取不到(因为有邻近边界的格子)
int N = n * n, M = N * 2;
h = new int[N + 1];
Arrays.fill(h, -1);
e = new int[M];
ne = new int[M];
List<Integer> half = new ArrayList<>(); // 存某一种颜色的格子
// 开始建图
for (int x = 1; x <= n; ++x) {
// 只取一种颜色(奇数行奇数列或偶数行偶数列)的格子
for (int y = (x & 1) == 1 ? 1 : 2; y <= n; y += 2) {
// 跳过禁止放置的格子
if (g[x][y]) continue;
// 给格子编号 范围在[1,n*n]
int u = (x - 1) * n + y;
half.add(u);
// 对另一种颜色的格子尝试连边
for (int[] DIR : DIRS) {
int nx = x + DIR[0], ny = y + DIR[1];
if (nx < 1 || nx > n || ny < 1 || ny > n || g[nx][ny]) continue;
int v = (nx - 1) * n + ny;
add(u, v);
}
}
}
matchs = new int[N + 1];
vis = new boolean[N + 1];
int ans = 0;
for (int u : half) {
Arrays.fill(vis, false);
if (find(u)) ++ans;
}
System.out.println(ans);
}
}
评论区