骑士共存问题

解题思路

本题是要求放最多的马使得所有马不会相互攻击，如果将所有能相互攻击的马之间连一条边，将所有奇数格作为左部节点，将所有偶数格作为右部节点，这就是一个二分图，且要求选中的点之间都不存在边，也就是求二分图的最大独立集，可以用匈牙利算法来求。

但是本题的数据比较大，用匈牙利算法会被卡常数，因此需要用更快的算法实现，可以用网络流求最大权独立集的方法来求，而 dinic 算法比匈牙利算法快很多，不用担心超时。

最大权独立集 $=$ 总权值 $-$ 最小权点覆盖集，因此我们需要求出最小权点覆盖集，用固定做法就行，从源点向所有左部节点连一条容量是权值的边，从所有右部节点向汇点连一条容量是权值的边，左部节点和右部节点之间的边容量是 $+\infty$。最小割就是最小权点覆盖。

本题每个点是没有权值的，求的也是最大独立集的点数，因此可以认为每个点的权值都是 $1$。这样就能求出最小点覆盖的点数，对应求出最大独立集的点数，两者是互补的。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010, M = 400010, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
bool g[210][210]; //地图，记录每个点是不是障碍

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

int get(int x, int y) //给每个格子一个对应的编号
{
    return (x - 1) * n + y;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往汇点能传输的最大流量，传输上限是 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //最小割
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    S = 0, T = n * n + 1; //源点、汇点
    int sum = n * n - m; //记录没有障碍的格子数量
    while(m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = true; //记录所有障碍格子
    }

    int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2}, dy[8] = {2, -2, 2, -2, 1, -1, 1, -1}; //马字步的方向向量
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            if(g[i][j]) continue; //跳过所有障碍格子

            if(i + j & 1)
            {
                add(S, get(i, j), 1); //从源点向奇数格连一条容量是 1 的边
                for(int k = 0; k < 8; k++)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 1 && x <= n && y >= 1 && y <= n && !g[x][y])
                        add(get(i, j), get(x, y), INF); //从每个奇数格向能到达的偶数格连一条容量是 INF 的边
                }
            }
            else add(get(i, j), T, 1); //从所有偶数格向汇点连一条容量是 1 的边
        }

    printf("%d\n", sum - dinic()); //最大独立集 = 总点数 - 最小点覆盖（最小割）

    return 0;
}