【匈牙利算法】棋盘覆盖

题目

372. 棋盘覆盖 - AcWing题库

---

给定一个 $N$ 行 $N$ 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 $2$ 、宽度为 $1$ 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数 $N$ 和 $t$ ，其中 $t$ 为禁止放置的格子的数量。

接下来 $t$ 行每行包含两个整数 $x$ 和 $y$ ，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

输出格式

输出一个整数，表示结果。

数据范围

$1 \le N \le 100$ ,
$0 \le t \le 100$

输入样例：

8 0

输出样例：

32

解题

方法一：二分图最大匹配 匈牙利算法

思路

咱自己也没搞明白这题是怎么 想到 二分图最大匹配的，所以以下只解释怎么把该题 转换 为二分图最大匹配问题。

首先把所有格子看成点，然后对相邻的两个格子（可以放骨牌）连上一条边，例如：

这样的棋盘（黑色代表禁止放置的格子，为方便起见对所有格子标了序号）可以建出以下图：

这样以来这个问题就转换成为了 在选择的边不含公共点的前提下，最多能取多少条边 ，也就是 最大匹配 问题。

那么如何证明这个图是二分图呢？证明这个图是二分图就等同于证明这个图可以被二染色。

这个图当然可以被二染色，如下：

只要按照这种规则，所有 $n \times m$ 的矩阵都可以被二染色。且所有奇数行奇数列或偶数行偶数列的格子为一种颜色，所有奇数行偶数列或偶数行奇数列的格子为另一种颜色。

自此以来，这个问题就被转换为了二分图求最大匹配问题，可以直接用匈牙利算法求解。

代码

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);
    }
}