题解：P13472 [GCJ 2008 #3] No Cheating

· · 题解

题意

有一个教室，座位网格状排列，其中一些是坏的。如果一个人的左右邻座或前一排的左右邻座有人就会作弊。问教室做多安排多少人。

分析

图论建模：二分图的最大独立集。

建立二分图：奇数列和偶数列的座位可以看成一个二分图，连边表示不能同时坐人，根据题意这确实是二分图。

我们从奇数列的没坏座位向和它有矛盾的偶数列的座位连有向边（注意不仅要连当前行、前一排的左右邻座，后面的左右邻座也是矛盾的）。

然后就是二分图匹配的板子。

实现

#include<bits/stdc++.h>
using namespace std;
const int K = 90,N = K * K,dx[] = {0,0,-1,-1,1,1},dy[] = {-1,1,-1,1,-1,1};
int a[K][K],mat[N];
int st[N];
vector<int> e[N];
int n,m;
bool dfs(int x)
{
    for(auto y : e[x])
    {
        if(st[y]) continue;
        st[y] = 1;
        if(!mat[y] || dfs(mat[y]))
        {
            mat[y] = x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    int t;
    cin>>t;
    for(int id = 1; id <= t; id ++)
    {
        memset(a,0,sizeof a);
        memset(e,0,sizeof e);
        memset(mat,0,sizeof mat);
        int ans = 0;
        cin>>n>>m;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                char c;
                cin>>c;
                if(c == 'x') ans += 1 - a[i][j];
                else a[i][j] = 1;
            }
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j += 2)
                if(a[i][j])
                    for(int k = 0; k < 6; k ++)
                    {
                        int x = i + dx[k],y = j + dy[k];
                        if(a[x][y]) e[(i - 1) * m + j].push_back((x - 1) * m + y);
                    }
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                memset(st,0,sizeof st);
                if(dfs((i - 1) * m + j)) ans ++;
            }
        cout<<"Case #"<<id<<": "<<n * m - ans<<endl;
    }
    return 0;
}