# 前置知识

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

# 最大独立集

图的最大独立集：从图中选出最多的点，使得选出的点中任意两点之间没有边。
图的最大团：从图中选出最多的点，使得选出的任意两点之间都有边。
根据定义，我们也能发现，这两个概念是互补的。
补图：就是把原图中所有边拆开，所有未连接的边连上。
那么，原图中的最大独立集就是补图中的最大团。

# 二分图中求最大独立集

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

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

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

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

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

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

经典必会 AcWing算法提高课匈牙利算法二分图的最大独立集问题