为啥第二个样例是29啊真的离谱
查看原帖
为啥第二个样例是29啊真的离谱
657442
wusihao1931楼主2022/9/27 16:12
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 210;

int n, m, k;
bool spoil[N][N];
bool st[N * N];
int idx[N][N];
int match[N * N];
int h[N * N], e[N * N * N], ne[N * N * N], edx;
int dx[8] = {-3, -3, -1, -1, 1, 1, 3, 3};
int dy[8] = {-1, 1, -3, 3, -3, 3, -1, 1};

void add(int a, int b)
{
    e[edx] = b;
    ne[edx] = h[a];
    h[a] = edx;
    edx ++ ;
}

bool find(int a)
{
    for (int i = h[a]; i != -1; i = ne[i])
    {
        int b = e[i];
        if (st[b]) continue;
        st[b] = true;

        if (match[b] == -1 || find(match[b]))
        {
            match[b] = a;
            return true;
        }
    }
    
    return false;
}

int main()
{
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    memset(match, -1, sizeof match);
     
    for (int i = 1, t = 0; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            idx[i][j] = ++ t;
    
    int cnt = 0;        
    for (int i = 1; i <= k; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        if (!spoil[a][b])
        {
            cnt ++ ;
            spoil[a][b] = true;
        }
    }
            
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (!spoil[i][j] && (i + j) & 1)
            {
                for (int k = 0; k < 8; k ++ )
                {
                    int a = i + dx[k], b = j + dy[k];
                    if (a < 1 || a > n || b < 1 || b > m || spoil[a][b]) continue;
                    add(idx[i][j], idx[a][b]);
                }
            }
        }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if ((i + j) & 1 && !spoil[i][j])
            {
                memset(st, 0, sizeof st);
                int a = idx[i][j];
                if (find(a)) res ++ ;
            }

    cout << n * m - res - cnt << endl;
    
    return 0;
}
2022/9/27 16:12
加载中...