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