小指针
2022/10/01阅读:86主题:凝夜紫
【图论专题】二分图中的最大独立集问题的求解思路
前置知识
最大独立集
「图的最大独立集」:从图中选出「最多」的点,使得「选出的点中 任意两点之间没有边」。
「图的最大团」:从图中选出「最多」的点,使得「选出的 任意两点之间都有边」。
根据定义,我们也能发现,这两个概念是「互补」的。 「补图」:就是把原图中所有边拆开,所有未连接的边连上。
那么,「原图中的最大独立集就是补图中的最大团」。
二分图中求最大独立集
(前提条件是必须「在二分图中」下面的性质才能成立!!!)
首先,明确目标是「我们要选出最多的点,使得选出点中,任意两点之间是没有边的」,等价于是「选出最少的点,假如消除这些点,会使图中不存在任何一条边,我们把这些点去掉,剩下的就构成了最大独立集」。
这里有点脑筋急转弯,当我们「把 二分图中 所有能构成边的点 去掉,那么剩下的点 就一定没法 再构成任何一条边」,而我们的目标是让「剩下的点最多」,那么「去掉的点就应该最少」。
而「选出最少的点,使这些点能构成所有的边」,其实就是我们前置文章中的概念「最小覆盖点集」。并且在前置文章中,我们已经知道「在二分图中,最小覆盖点集就等价于最大匹配数量」。
因此,我们就得出了「二分图中最大独立点集」的求法:「只需要求出最大匹配,然后用总点数减去最大匹配数」即可。
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;
}
作者介绍