骑士放置

二分图最大独立集 T3 378. 骑士放置 - AcWing题库 给定一个 $N\times M$ 的棋盘，有一些格子禁止放棋子。

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

输入格式

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

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

输出格式

输出一个整数表示结果。

数据范围

$1\le N,M\le 100$

输入样例：

2 3 0

输出样例：

4

思路

最大独立集问题是图论研究中的一个重要问题，具有广泛的应用。 一个图G(V, E)的顶点集子集I称为图G的一个独立集，是指：I中任意两个顶点之间没有边相连。而最大独立集是包含最多顶点的独立集。

根据König定理：在一个二分图中，最大匹配的大小等于最小顶点覆盖的大小。 最小顶点覆盖是指一个顶点子集，使得原图中的每一条边都至少有一个端点在这个子集中，并且子集的大小最小。 由于二分图中的顶点数等于独立集和顶点覆盖的和，所以可以推出最大独立集的大小等于 总顶点数减去最小顶点覆盖（也就是最大匹配）的大小。

因此只需要求出最大匹配的数量, 就可以得出最大独立集数量。

该题若把每个格子能跳过去的格子之间建一条边, 那么无法攻击到的格子就是之间不存在边的格子, 满足这个条件的格子集合就是最大独立集。

本题的矩形排列的格子可以设行数加列数 $i+j$ 为偶数的分为一边, 为奇数的分到另一边, 形成二分图, 而根据马走日的模式, 从一个点只能通过 +1+2 的方式到达另一个点, 因为 一个数+奇数 后会改变奇偶性, 故该图一定是二分图。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
PII match[N][N];
bool g[N][N];
int n,m,k;
int d[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
bool st[N][N];
 
bool find(int x, int y)
{
    for(int i = 0; i < 8; i++){
        int a = x + d[i][0], b = y + d[i][1];
        if(a < 1 || a > n || b < 1 || b > m) continue;
        if(g[a][b] || st[a][b]) continue;
        st[a][b] = true;
        if(!match[a][b].first || find(match[a][b].first, match[a][b].second))
        {
            match[a][b] = {x,y};
            return true;
        }
    }
    return false;
}
 
 
int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < k; 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(!((i + j) & 1) && !g[i][j])
            {
                memset(st, 0, sizeof st);
                if(find(i,j)) res++;
            }
    cout << n*m - res - k << endl;
    return 0;
}