侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【匈牙利算法】棋盘覆盖

GabrielxD
2023-03-16 / 0 评论 / 0 点赞 / 532 阅读 / 1,021 字
温馨提示:
本文最后更新于 2023-03-16,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

372. 棋盘覆盖 - AcWing题库


给定一个 NNNN 列的棋盘,已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 22 、宽度为 11 的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数 NNtt ,其中 tt 为禁止放置的格子的数量。

接下来 tt 行每行包含两个整数 xxyy ,表示位于第 xx 行第 yy 列的格子禁止放置,行列数从 11 开始。

输出格式

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

数据范围

1N1001 \le N \le 100 ,
0t1000 \le t \le 100

输入样例:

8 0

输出样例:

32

解题

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

思路

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

首先把所有格子看成点,然后对相邻的两个格子(可以放骨牌)连上一条边,例如:

image-20230316232158290

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

image-20230316232339267

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

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

这个图当然可以被二染色,如下:

image-20230316233015587

只要按照这种规则,所有 n×mn \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);
    }
}
0

评论区