MLE求助

P3355 骑士共存问题

emo_male_god @ 2023-07-05 15:08:02

#include <iostream>

using namespace std;

const int N = 205, dx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
int n, m, tot, T, link[N * N], road[N * N], cnt, nums[N][N];
bool ban[N][N], map[N * N][N * N];

bool Find(int v)
{
    for (int i = 1; i <= tot; i ++ )
    {
        if (map[v][i] && road[i] != T)
        {
            road[i] = T;
            if (link[i] == 0 || Find(link[i]))
            {
                link[i] = v;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int x, y, i = 1; i <= m; i ++ )
    {
        scanf("%d%d", &x, &y);
        ban[x][y] = 1;
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (!ban[i][j]) nums[i][j] = ++ tot;

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            if (ban[i][j]) continue;
            for (int x, y, k = 1; k <= 8; k ++ )
            {
                x = i + dx[k];y = j + dy[k];
                if (x >= 1 && x <= n && y >= 1 && y <= n && !ban[x][y])
                {
                    map[nums[i][j]][nums[x][y]] = true;
                }
            }
        }
    }

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            if (!ban[i][j] && (i + j) % 2)
            {
                T ++ ;
                if (Find(nums[i][j])) cnt ++ ;
            }
        }
    }

    printf("%d\n", tot - cnt);
    return 0;
}

by CQWDX @ 2023-07-05 15:15:00

邻接矩阵 MLE

邻接表 TLE80

链式前向星AC


|