在一个 n∗n 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。 棋盘上某些方格设...

下面的分析试图以「极致的深度」来阐述此题的本质思路、为何能用最大流/最大匹配求解，以及代码内部各个关键细节的运作原理。我们会从问题建模、图论核心思想、再到代码流程（尤其是 Dinic 算法本身）进行层层剖析，以期从原理、实现到复杂度都给出尽可能深入的解释。

---

一、问题本质：最大独立集（Maximum Independent Set）与二分图匹配

1. 问题描述回顾

• 我们有一个 $n \times n$ 的国际象棋棋盘，其中某些格子上放置了障碍（不可放置骑士）。
• 需要在剩余（无障碍的）方格上放骑士，使得没有任意两个骑士可以互相攻击。
• 题目问能放置的骑士数目的最大值。

骑士的攻击特点：国际象棋中的马（骑士）走日字，具体可攻击到相对位置 $(\pm2, \pm1)$ 或 $(\pm1, \pm2)$ 的格子。

---

2. 从「无冲突放置」到「图上的最大独立集」

若把每个“可放置的格子”看作图中的一个「顶点」，那么「两个格子能被同一个骑士攻击」就等价于在这两个顶点间连一条边——意味着如果选择了这两个顶点同时放骑士就会冲突。这种图可以称为「冲突图」或「冲突关系图」。

• 我们希望选出尽量多的顶点（方格）而不包含任意一条边的两个端点（即不出现冲突）。
• 这正是「图中的最大独立集（Maximum Independent Set）」问题：在图里选出最大的点集，使得其中任意两点之间都没有边相连。

最大独立集是一个 NP-困难问题，但这里之所以能够在多项式时间内解决，是因为这个冲突图有特殊结构——它实际上是一个二分图。我们先从棋盘颜色与骑士走法的属性谈起。

2.1 国际象棋骑士与“黑白格”的二分图结构

国际象棋棋盘本身是黑白相间的（或者说，我们可以给它 2-染色：令 $(x + y)$ 奇偶性相反的格子分属不同颜色）。这是一个经典结论：

• 骑士只能在“黑”格与“白”格之间跳跃，它无法一直留在同色格子上反复跳动。
• 因此，如果我们将所有可用的方格按照 $(x + y)$ 的奇偶性分为两部分（例如把 $x + y$ 为奇数的格子视作“左集合”，偶数的格子视作“右集合”），那么任意一个骑士的可达攻击关系只能在「左集合」和「右集合」之间产生边。

这说明了：冲突图是一个二分图。二分图的一个重要性质是：** 它的最大独立集大小 = 顶点总数 - 最小顶点覆盖数**（Kőnig 定理）。而最小顶点覆盖数又与最大匹配数相等，亦即在二分图中：

$$\boxed{\text{最大独立集数} = \text{顶点总数} - \text{最大匹配数} \quad(\text{Kőnig 定理})}$$

因此，为了求解题目中的“最大可同时放置的骑士数”，等效于找该二分图的最大独立集；也等效于在该二分图中先求出最大匹配，再用总顶点数减去它，得到结果。

---

3. 将问题转化为最大流 / 最大匹配

3.1 为什么用最大流

二分图最大匹配，可以用经典的「匈牙利算法」「Hopkroft–Karp 算法」或「最大流算法」来做。因为二分图匹配可以视为一个网络流问题：

1. 建立一个「源点 S」连向「左集合」的每个顶点（容量设为 1），
2. 「左集合」与「右集合」之间，根据“是否能攻击”连边，若骑士能跳到对方那一格，则在对应的两个顶点间连边，并将该边容量设为无穷（或一个足够大的数），表示它只要能连，就不想限制它的通量，但真正限制流量的是两侧的顶点只能各通过 1。
3. 「右集合」每个顶点再连向「汇点 T」，容量也设为 1。

通过这样构造，任意一条在二分图中实际用到的「匹配边」都会从源点 S 经过「左顶点 -> 右顶点」一直流到汇点 T，但受限于「左顶点」和「右顶点」到达汇点 T 的容量都只有 1，所以最终能流多少，便对应能匹配多少对顶点。也就是说，这样的最大流值恰好等于这张二分图的最大匹配数。

3.2 加入障碍的处理

• 障碍格子无法放骑士，可视为在二分图中「删除对应顶点」。
• 代码中是通过记录障碍格子，直接跳过对它的处理，在建立图时，不会把该格子连入网络中。

---

二、代码核心思路剖析

题目给的完整代码如下（已省略多余注释），我们先看它的结构，再做深入解释：

cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 40010, M = 400010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
bool g[210][210];

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

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];

    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs())
        while (flow = find(S, INF)) r += flow;
    return r;
}

int main()
{
    scanf("%d%d", &n, &m);
    S = 0, T = n * n + 1;
    memset(h, -1, sizeof h);

    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = true;
    }

    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

    int tot = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (g[i][j]) continue;     // 如果是障碍就跳过
            if ((i + j) & 1)
            {
                // 左集合的顶点连向 S
                add(S, get(i, j), 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);
                }
            }
            else
            {
                // 右集合的顶点连向 T
                add(get(i, j), T, 1);
            }
            tot++;
        }

    // 最大独立集 = tot - 最大匹配
    printf("%d\n", tot - dinic());
    return 0;
}

下面分步骤探讨：

---

1. 变量与数据结构

• n, m：棋盘大小 $n$ 和障碍个数 $m$。
• S, T：源点和汇点的编号。这里为了在网络流里构图，令：
  • S = 0
  • T = n*n + 1
• h[]：每个点的邻接表起始边索引，若 h[u] = i，表示从节点 $u$ 出发的第一条边在边数组 e 里是下标 $i$。
• e[]：存储边对应的「目标节点」。
• f[]：存储边的剩余容量（flow capacity）。
• ne[]：存储边的下一条同起点边的索引，用以链接到邻接表中。
• idx：边的编号索引，每加入一条边 idx 自增 2（因为是正向 + 反向边一起加）。
• d[]：Dinic 算法中的分层距离数组（层次 graph 的深度）。
• cur[]：当前弧指针，Dinic 算法优化用，避免重复从头寻找可行边。
• g[x][y]：记录棋盘上坐标 $(x, y)$ 是否有障碍，若 true 代表障碍。

---

2. get(x, y) 函数

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

这是将棋盘二维坐标 $(x, y)$ 转化为在图或网络中的编号。因为我们打算把棋盘上的每个位置对应图中的一个顶点编号范围是 $[1..n*n]$。
具体地：

• 行号 x 范围是 [1..n]
• 列号 y 范围是 [1..n]
• 整个棋盘共有 $n * n$ 个格子；
• 若没有障碍，每个格子都对应一个顶点，从 1 到 n*n；
• 因为源点 S 用 0 号，汇点 T 用 n*n + 1 号，所以总共 n*n + 2 个点。

---

3. add(a, b, c) 函数

cpp
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

• 给图中添加从 a 到 b 的正向边，容量是 c；同时加一条从 b 到 a 的反向边，容量初始为 0。
• 这是构建「残量网络」的标准做法。流算法里，正向边若被用掉一些流量，就会把这部分流量变成反向可退还流（在反向边中体现）。

---

4. 构图关键逻辑（main 函数中部）

cpp
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    {
        if (g[i][j]) continue;    // 障碍就不处理

        if ((i + j) & 1)
        {
            // (i,j) 在左集合 => 连 S -> (i,j)
            add(S, get(i, j), 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])
                {
                    // 连 (i,j) -> (x,y)，容量无穷
                    add(get(i, j), get(x, y), INF);
                }
            }
        }
        else
        {
            // (i,j) 在右集合 => 连 (i,j) -> T
            add(get(i, j), T, 1);
        }
        tot++;
    }

• 先用 if (g[i][j]) continue; 跳过障碍位置。
• (i + j) & 1 判定奇偶：若 $(x + y)$ 为奇数，则该格子属于“左集合”；偶数则属于“右集合”。
• 左集合顶点用边 S -> 该点，容量 1；右集合顶点用边 该点 -> T，容量 1。
• 在左集合点与右集合点之间，如果它们能互相跳跃（即满足骑士移动），我们连一条容量 = INF （常数 $10^8$ 亦可）的边。
• tot++ 统计非障碍格子数目。

为什么左集合到右集合边容量要设无穷？
因为真正限制流量的本质是“一个点只能被匹配一次”。对于二分图匹配来说，每个顶点最多匹配一条边，这在网络流模型里体现在“顶点的入或出容量 = 1”。故只要左右顶点各自的容量限制是 1，它们之间那条边容量再大也只会实际通过 1 单位流。将那条边设得很大，可以理解为“如果这两点之间存在可攻击关系，就可以随意连通，但具体流量的限制依赖两端顶点本身只能通过 1 的流。”

---

5. Dinic 最大流核心

在 main() 最后，通过：

cpp
int flow = dinic();          // 求最大流
int ans = tot - flow;        // 最大独立集 = 总点数 - 最大匹配
printf("%d\n", ans);

就得到最终答案。dinic() 函数则是实现 Dinic 算法，代码结构包括两个关键子函数：

1. bfs()：构建分层图（level graph）。
   • 从源点出发，按照“当前边是否还有剩余容量”来决定可否把下一个点放到队列里。
   • 将每个可访问节点记录一个“层数” d[ver] = d[t] + 1。一旦找到汇点，就可以停止 BFS 构建层次的过程（因为之后的增广只需要到达汇点所在层）。
2. find(u, limit)：在分层图中找从 u 到 T 的可行增广路径，并尽可能把容量利用最大。
   • 这一步往往用 DFS 的形式实现。
   • cur[u] 是当前弧指针，用于减少重复遍历无效边。
   • 若 u == T，说明找到了一条增广到汇点的路径，可以返回本次可增的流量 limit。
   • 否则在邻接表中扫描所有出边，若满足层次约束 d[ver] == d[u] + 1 且该边 f[i]（剩余容量） > 0，则尝试增广。
   • 增广成功后，就会更新残量网络（f[i] -= t; f[i^1] += t;）并累加到 flow。

Dinic 算法的复杂度在二分图匹配场景常可达到 $O(\sqrt{V} E)$ 或更好（对于一般网络流是 $O(\min(V^{2/3}, E^{1/2}) E)$ 的常见分析）。在本题 $n \le 200$，实际 $V \approx n^2$，$E$ 量级也是 $n^2$ 内的一些常数倍，所以能在可接受时间内跑完。

---

三、深层本质：从最大匹配到最大独立集

从 Kőnig 定理 来看：

1. 最大匹配 = 最小顶点覆盖（在二分图中）。
2. 在图中选出一个「最小的能覆盖所有边的点集」，这个大小也就是最大匹配数。
3. 我们要的是「最大独立集」，它和「最小顶点覆盖」互为补集： $$\max \text{ 独立集} = \text{(所有非障碍顶点数)} - \min \text{ 顶点覆盖} = \text{(所有非障碍顶点数)} - \text{最大匹配}.$$

为什么这样能确保“最多的骑士互不攻击”？

• 骑士冲突对应图里的边；如果一条边的两个端点都选上了，那就冲突。
• 最小顶点覆盖是一种“最少数量的点”就可以和所有边都相邻；把它从棋盘里挑走以后，剩下的点必然不会产生冲突（因为如果剩下的点之间有一条边，就意味着那条边的两个端点都没被覆盖，但那条边应该被最小顶点覆盖集覆盖矛盾了）。
• 既然最小顶点覆盖集大小 = 最大匹配数，删去这么多点后能够保证边不出现；故剩下的点就是一个「不包含任何相邻边」的最大集合，即最大独立集。

---

四、要点总结与思维提升

1. 骑士在棋盘上的攻击关系天生构成二分图。它所依赖的是「骑士只能在不同颜色（奇偶和）间跳跃」的特性。
2. 求最大独立集通常很难，但在二分图里可以借助Kőnig 定理与最大匹配高效解决。
3. 障碍的引入只需要在构图时「跳过障碍格子」，不向图中添加该顶点以及相关边即可。
4. 网络流与二分图匹配之间的对应关系：
   • 左边集合的点（容量约束为 1） -> 右边集合的点（无限容量边） -> 汇点（容量约束为 1）。
   • 最终的最大流量就是最大匹配数。
5. Dinic 算法构建层次图 + 块流增广的一套流程，在本题规模下完全可行。

从更高的抽象来看，这道题所体现出的思维核心，是将「互相冲突不可同时选」的问题，巧妙地映射为二分图的边，然后利用二分图的「最大匹配」<->「最小顶点覆盖」<->「最大独立集」三者间的等价关系，结合经典最大流算法达成。无论换成什么棋盘（只要满足能 2-染色）或其他类似冲突关系，都可以采用这一路径。

---

五、结论

• 答案即：在无障碍的格子总数（tot）之下，减去该二分图的最大匹配数（dinic()计算结果），就能得到棋盘上能放置且互不攻击的骑士最大数量。
• 代码在实现上，核心是构造网络 + Dinic；本质原理是最大独立集 = 总节点 - 最大匹配（Kőnig 定理在二分图中的经典应用）。

这样，我们就从骑士攻击关系的二分图性质，连接到最大匹配与最大独立集的等价，再到具体网络流实现，完整地得出了题目的求解过程与算法理由。上述就是本题的「本质洞察」与「核心思路」。