题解：P15890 [COCI 2025/2026 #6] 抄写 / Prepisivanje

· · 题解

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

::::