最大流=最小割

ISAP+当前弧优化巨快

解题思路

不难看出,马能攻击到的点和它本身所在的点黑白颜色不同,所以我们考虑建立二分图进行匹配

建图

  • 设$0$为原点,$n ^ 2 + 1$为汇点,把格子上的每一个点映射到$[1, n ^ 2]$
  • 对于$\forall i \in black$,如果$i$点没有障碍,从$0$向$i$建立容量为$1$的边
  • 对于$\forall j \in white$,如果$j$点没有障碍,从$j$向$n ^ 2 + 1$建立容量为$1$的边
  • 对于$\forall i \in black$,从$i$向能攻击到的八个白点建立容量为$\infty$的边

然后跑最大流,用总格数-障碍数-最大流即可

代码

看有人发匈牙利和dinic的题解,说奇数建图和偶数建图有一种过不了,但是用ISAP两种都能过。

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int MAXN = 205;
const int INF = 0x3f3f3f3f;
const int DIRX[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int DIRY[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

int n, m;
bool trap[MAXN][MAXN];

int ID(int x, int y) {
    return (x - 1) * n + y;
}

struct Edge{
    int to, val;
    Edge *next, *ops;
    Edge(int to, int val, Edge *next): to(to), val(val), next(next){}
};

Edge *head[MAXN * MAXN], *cur[MAXN * MAXN];

void AddEdge(int u, int v, int w) {
    head[u] = new Edge(v, w, head[u]);
    head[v] = new Edge(u, 0, head[v]);
    head[u]->ops = head[v]; head[v]->ops = head[u];
}

int dep[MAXN * MAXN], gap[MAXN * MAXN], s, t, res;

void Bfs() {
    memset(dep, -1, sizeof(dep));
    memset(gap, 0, sizeof(gap));
    dep[t] = 0; gap[0]++;
    queue<int> q; q.push(t);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (Edge *e = head[u]; e; e = e->next) {
            int v = e->to;
            if (dep[v] != -1) continue;
            q.push(v);
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}

int Dfs(int u, int flow) {
    if (u == t) {
        res += flow;
        return flow;
    }
    int used = 0;
    for (Edge *&e = cur[u]; e; e = e->next) {
        int v = e->to;
        if (e->val && dep[v] == dep[u] - 1) {
            int mi = Dfs(v, min(e->val, flow - used));
            if (mi) {
                used += mi;
                e->val -= mi;
                e->ops->val += mi;
            }
            if (used == flow) return used;
        }
    }
    gap[dep[u]]--;
    cur[u] = head[u];
    if (gap[dep[u]] == 0) dep[s] = n * n + 3;
    dep[u]++;
    gap[dep[u]]++;
    return used;
}

void Work() {
    memcpy(cur, head, sizeof(head));
    res = 0;
    Bfs();
    while (dep[s] <= n * n + 2) Dfs(s, INF);
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    s = 0; t = n * n + 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        trap[x][y] = true;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i + j) % 2 == 0) {
                if (!trap[i][j]) AddEdge(0, ID(i, j), 1);
                for (int k = 0; k < 8; k++) {
                    int x = i + DIRX[k], y = j + DIRY[k];
                    if (x < 1 || x > n || y < 1 || y > n) continue;
                    AddEdge(ID(i, j), ID(x, y), INF);
                }
            } else {
                if (!trap[i][j]) AddEdge(ID(i, j), n * n + 1, 1);
            }
        }
    }
    Work();
    cout << n * n - m - res << endl;
    return 0;
}