显然有种贪心思路是染色，然后看每个连通块内的种类更多的颜色数。

但会被下面这组卡飞（感谢阎帝给出的 hack）：

3 8
11011011
10011001
00000000

答案显然是 8，但染色贪心会输出 7。

所以贪心不可取。

首先肯定不能贪心，你如果见缝插针地放坏学生。

前面放的坏学生是会影响后面是否能放坏学生的。

所以一个坏学生相当于“控制”了周围的四格，这一种可选择、不可重复的匹配关系，让我们联系到二分图匹配。

求最多可放的坏学生数量，就相当于求最多不相关可成匹配，也就是最大独立集。

我们先将不可放人的格子，和好学生格子以及其周围四格标记，剩余未标记的格子可以与附近四格的格子连边，表示一种可以匹配的关系。

推荐本 oj 一道题：https://www.oirush.cn/p/P2186

但二分图讲究单向匹配单项寻找，所以将网格分为黑白棋盘格，黑格向白格连边。

最后得出的最大匹配，也就是最小覆盖，而最大独立集 = 总数 - 最小覆盖。

因为左右点各要枚举一次，时间复杂度为 $O(N^2M^2)$，实测常数小飞天速度。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 90;
bool v[N][N];
char s[N];
int n, m;

vector<int> G[N * N];
int match[N * N], chw[N * N], tsp;

int get_num(int x, int y) {
	return (x - 1) * m + y;
}

bool findmuniu(int x) {
	for (int y : G[x]) {
		if (chw[y] != tsp) {
			chw[y] = tsp;
			if (match[y] == 0 || findmuniu(match[y])) {
				match[y] = x;
				return 1;
			}
		}
	}
	return 0;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	memset(v, 0, sizeof(v));
	int sumo = 0, sumt = 0;
	
	for (int i = 1; i <= n; i ++) {
		cin >> (s + 1);
		for (int j = 1; j <= m; j ++) {
			if (s[j] == '1') {
				v[i][j] = 1;
			}
			else if (s[j] == '2') {
				v[i][j] = 1;
				sumt ++;
				if (i - 1 >= 1 && v[i - 1][j] == 0) {
					v[i - 1][j] = 1;
				}
				if (i + 1 <= n && v[i + 1][j] == 0) {
					v[i + 1][j] = 1;
				}
				if (j - 1 >= 1 && v[i][j - 1] == 0) {
					v[i][j - 1] = 1;
				}
				if (j + 1 <= m && v[i][j + 1] == 0) {
					v[i][j + 1] = 1;
				}
			}
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) if (v[i][j] == 1) {
			sumo ++;
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) if (v[i][j] == 0 && ((i + j) % 2 == 0)) {
			int id = get_num(i, j);
			if (i - 1 >= 1 && v[i - 1][j] == 0) {
				G[id].push_back(get_num(i - 1, j));
			}
			if (i + 1 <= n && v[i + 1][j] == 0) {
				G[id].push_back(get_num(i + 1, j));
			}
			if (j - 1 >= 1 && v[i][j - 1] == 0) {
				G[id].push_back(get_num(i, j - 1));
			}
			if (j + 1 <= m && v[i][j + 1] == 0) {
				G[id].push_back(get_num(i, j + 1));
			}
		}
	}
	
	tsp = 0;
	memset(chw, 0, sizeof(chw));
	memset(match, 0, sizeof(match));
	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) if (v[i][j] == 0 && ((i + j) % 2 == 0)) {
			int id = get_num(i, j);
			tsp = id;
			if (findmuniu(id)) {
				ans ++;
			}
		}
	}
	
	cout << (n * m - sumo - ans + sumt) << "\n";
	
	return 0;
} 

Solution

一道网格图上的二分图最大独立集问题。

首先分析题意。教室中有三种座位：2 表示行为良好的学生（已就坐，不担心作弊），1 表示禁止入座，0 表示空座位。调皮学生只能坐在空座位上。如果调皮学生的上、下、左、右四个方向中有任何其他学生（无论好坏），该调皮学生就会作弊。我们希望最大化教室中的总人数，且无人作弊。

注意到好学生之间可以相邻，因为好学生从不作弊。但对于调皮学生：

• 不能与好学生相邻；
• 不能与其他调皮学生相邻。

因此，所有与好学生相邻的空座位（0）实际上都不能坐人，否则该调皮学生就会与好学生相邻而作弊。我们可以在读入后立即将这些空座位标记为 1（禁止入座），从而排除掉它们。

处理完毕后，剩下的 0 座位构成一个图：每个 0 是一个点，若两个 0 座位相邻（四连通），则在它们之间连一条边。我们的目标是选择尽可能多的点（安排调皮学生），使得选出的点之间没有边相连，即求这个图的最大独立集。最终答案等于 好学生人数 + 该最大独立集的大小。

由于网格图是二分图（按行列坐标之和的奇偶性划分），我们可以用匈牙利算法求出最大匹配。设剩余可用 0 的个数为 $V$，最大匹配数为 $M$，则最大独立集大小为 $V - M$。总答案即为 $ans = \text{好学生数} + V - M$。匈牙利算法的时间复杂度为 $O(V \cdot E)$，本题中 $n,m \le 80$，$V \le 6400$，足以通过。

具体实现时，先将所有 2 计数并染黑四周的 0，再将所有剩余的 0 计数。建图时只需从偶点（$(i+j)$ 为偶数）向相邻的奇点连有向边，运行匈牙利算法求匹配数。最终输出 ans - cnt 即可。

::::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int N = 80;
int n,m,a[N + 5][N + 5],p[N * N + 5],ans,cnt;
int vis[N * N + 5];
string s;
vector<int>edge[N * N + 5];
int id(int x,int y){return (x - 1) * m + y;};
bool dfs(int cur,int t){
    for(auto son : edge[cur]){
        if(vis[son] != t){
            vis[son] = t;
            if(!p[son] || dfs(p[son],t)){
                p[son] = cur;
                return true;
            }
        }
    }
    return false;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> s;
        for(int j = 1;j <= m;j++)
            a[i][j] = s[j - 1] - '0';
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(a[i][j] == 2){
                ans++;
                a[i - 1][j] = (a[i - 1][j] == 0 ? 1 : a[i - 1][j]);
                a[i][j - 1] = (a[i][j - 1] == 0 ? 1 : a[i][j - 1]);
                a[i + 1][j] = (a[i + 1][j] == 0 ? 1 : a[i + 1][j]);
                a[i][j + 1] = (a[i][j + 1] == 0 ? 1 : a[i][j + 1]);
            }
        }
    }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            ans += (a[i][j] == 0);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(a[i][j] == 0 && (i + j) % 2 == 0){
                if(i < n && a[i + 1][j] == 0)
                    edge[id(i,j)].push_back(id(i + 1,j));
                if(i > 1 && a[i - 1][j] == 0)
                    edge[id(i,j)].push_back(id(i - 1,j));
                if(j < m && a[i][j + 1] == 0)
                    edge[id(i,j)].push_back(id(i,j + 1));
                if(j > 1 && a[i][j - 1] == 0)
                    edge[id(i,j)].push_back(id(i,j - 1));
            }
        }
    }
    for(int i = 1;i <= n * m;i++)
        if(((i - 1) / m + 1 + (i - 1) % m + 1) % 2 == 0 && a[(i - 1) / m + 1][(i - 1) % m + 1] == 0)
            cnt += dfs(i,i);
    cout << ans - cnt << '\n';
    return 0;
}

::::

分析

本题就是求二分图中的最大独立集。

把网格中的 $0$ 按照 $(i+j) \mod 2$ 的奇偶性染色，即进行交替染色，形成两个颜色集合。题目度约束条件是 $2$ 位置旁边的 $0$ 不能坐，标记。将能坐的 $0$ 位置互相连边，则网格形成一个二分图，跑匈牙利算法可以得到最大匹配。

根据柯尼希定理，二分图的最小覆盖集等于最大匹配。

::::info[最小覆盖集] 点可以控制其发出的边。选择最少的点，可以控制所有的边，称选择的点最少的集合为最小覆盖集。 ::::

::::info[证明] 记 $\tau(G)$ 为最小点覆盖大小，$\nu(G)$ 为最大匹配边数。

• $\tau(G)\ge\nu(G)$。最大匹配的 $\nu(G)$ 条边两两无公共端点。要覆盖这些边，每条边至少选一个端点，故任意点覆盖至少 $\nu(G)$ 个点，$\tau(G)\ge\nu(G)$。

• $\tau(G)\le\nu(G)$

  取最大匹配 $M$。走交替路（即从左部未匹配点出发，依次走非匹配边、匹配边、非匹配边……）令 $Z$ 为这样走所有可达的点，$L_Z=Z\cap L$，$R_Z=Z\cap R$。构造点集 $K=(L\setminus L_Z)\cup R_Z$

  • $K$ 是点覆盖。假设存在边 $(u,v)$（$u\in L,v\in R$）未被覆盖，即 $u\in L_Z,\ v\notin R_Z$。交替路可到达 $u$，沿 $(u,v)$ 延伸即可到达 $v$（无论 $(u,v)$ 是匹配边或非匹配边），得 $v\in R_Z$，矛盾。

  • $|K|=|M|$。对任意匹配边 $(u,v)$，交替路到 $u$ 当且仅当到 $v$（匹配边正反向均可达）。故匹配边的两端要么全在 $Z$ 要么全不在 $Z$。未匹配左部点均在 $L_Z$（出发地），未匹配右部点均不在 $R_Z$（否则存在增广路，与 $M$ 最大矛盾）。因此每条匹配边恰贡献一个端点到 $K$，$|K|=|M|=\nu(G)$。

于是存在大小为 $\nu(G)$ 的点覆盖，$\tau(G)\le\nu(G)$。综上 $\tau(G)=\nu(G)$。 ::::

又有最大独立集大小 = 总顶点数 - 最大匹配边数。

::::info[证明] 先证 $I$ 是独立集 $\iff$ $V \setminus I$ 是点覆盖。

• 若 $I$ 独立，则任意边 $(u,v)$ 的两端点不能全在 $I$ 中，故至少有一端在 $V \setminus I$ 里，即 $V \setminus I$ 覆盖所有边。

• 若 $K = V \setminus I$ 是点覆盖，则 $I$ 中任意两点不能相邻（否则该边的两端都不在 $K$ 中），故 $I$ 独立。

于是对任意独立集 $I$ 和点覆盖 $K = V \setminus I$，有 $|I| = |V| - |K|$。

取 $I$ 为最大独立集，则 $K$ 为某个点覆盖，故 $|K| \ge \tau(G)$，从而 $|I| \le |V| - \tau(G)$。

取 $K$ 为最小点覆盖，则 $I = V \setminus K$ 是独立集，故 $|I| \ge |V| - \tau(G)$。

因此得证。 ::::