前置知识

图论基础之二分图中最小覆盖问题的求解思路

最大独立集

「图的最大独立集」：从图中选出「最多」的点，使得「选出的点中 任意两点之间没有边」。

「图的最大团」：从图中选出「最多」的点，使得「选出的 任意两点之间都有边」。

根据定义，我们也能发现，这两个概念是「互补」的。 「补图」：就是把原图中所有边拆开，所有未连接的边连上。

那么，「原图中的最大独立集就是补图中的最大团」。

二分图中求最大独立集

（前提条件是必须「在二分图中」下面的性质才能成立！！！）

首先，明确目标是「我们要选出最多的点，使得选出点中，任意两点之间是没有边的」，等价于是「选出最少的点，假如消除这些点，会使图中不存在任何一条边，我们把这些点去掉，剩下的就构成了最大独立集」。

这里有点脑筋急转弯，当我们「把 二分图中 所有能构成边的点 去掉，那么剩下的点 就一定没法 再构成任何一条边」，而我们的目标是让「剩下的点最多」，那么「去掉的点就应该最少」。

而「选出最少的点，使这些点能构成所有的边」，其实就是我们前置文章中的概念「最小覆盖点集」。并且在前置文章中，我们已经知道「在二分图中，最小覆盖点集就等价于最大匹配数量」。

因此，我们就得出了「二分图中最大独立点集」的求法：「只需要求出最大匹配，然后用总点数减去最大匹配数」即可。

AcWing 378. 骑士放置

给定一个 N×M 的棋盘，有一些格子禁止放棋子。

问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。

「输入格式」
第一行包含三个整数 N,M,T，其中 T 表示禁止放置的格子的数量。

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

「输出格式」
输出一个整数表示结果。

数据范围

1≤N,M≤100

输入样例：

2 3 0

输出样例：

4

题目描述

国际象棋里面的“骑士”会按照“日”字形攻击，给出一个N*M的棋盘，棋盘上的某些格子不允许放棋子，问「棋盘上最多可以放多少个不能互相攻击的骑士」。

题目分析

如果我们把每个格子看做一个点，如果能从该格子能跳到另一个格子，则两个格子之间连接一条边。

进而，我们发现「如果把格子按照坐标进行奇偶划分为两个集合，那么能连边的两个点一定在不同集合，所以整个棋盘会形成一个二分图」。

根据上述模型，我们可以把题目的问题「最多可以放多少个不能互相攻击的棋子」变成「棋盘上最多可以有多少个棋子之间没有边」，也就是求「最大独立集」。

Code

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int n, m, t;
bool st[N][N], g[N][N];
PII match[N][N];

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

bool find(int x, int y) {
    for (int i = 0; i < 8; i ++ ) {
        int a = x + dx[i], b = y +  dy[i];
        if (a < 1 or a > n or b < 1 or b > m) continue;
        if (st[a][b] or g[a][b]) continue;
        st[a][b] = true;
        PII t = match[a][b];
        if (t.x == 0 or find(t.x, t.y)) {
            match[a][b] = {x, y};
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> t;
    for (int i = 0; i < t; i ++ ) {
        int a, b;
        cin >> a >> b;
        g[a][b] = true;
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            if (!g[i][j] and (i + j) % 2 != 0) {
                memset(st, 0, sizeof st);
                if (find(i, j)) res ++ ;
            }
        }
    }
    cout << n * m - res - t << endl;
    return 0;
}