# 神经突击车：题解

## 解法比较

出题人解法把可以成对处理的单位连边，求一般图最大匹配，并以单位数减匹配数得到答案。匹配边对应互不冲突的两单位分组；反过来，任何分组中的双单位组构成匹配，因此两种最优目标等价。出题人实现使用带花树处理奇环，下文解释这一归约及收缩、增广的说明。

使用邻接矩阵时，时间为 $O(n^3)$ ，空间为 $O(n^2)$ .Codex（GPT-6）负责数组、队列的实现与算法说明。

## 建模

把军队看作顶点，允许制造冲突的关系看作无向边。一次行动可以覆盖一条边的两个端点，或单独覆盖一个顶点。设一般图的最大匹配大小为 $\nu$ ，答案为

$$n-\nu$$

最大匹配的每条边用一次行动，剩余 $n-2\nu$ 个顶点各用一次，总计 $n-\nu$ .

反过来，在任意覆盖方案中不断删除多余行动，得到一个不能再删的方案。单点行动不能与其他行动共用顶点；边组成的每个非平凡连通分量都是星形：若某条边两端都还连着别的边，该边就可删除。每个星形任选一条边，得到一个匹配。一个有 $v$ 个顶点的星形用了 $v-1$ 次行动，单点用了 $1$ 次，因此若剩余行动数为 $k$ ，这个匹配有 $n-k$ 条边。于是 $n-k\le\nu$ ，任何方案都不可能优于 $n-\nu$ .

## 一般图最大匹配

关系图可能含奇环，不能直接套用二分图匹配。参考程序使用 Edmonds 缩花算法：

1. 从一个未匹配顶点出发，按“非匹配边、匹配边”交替扩展交错树。
2. 到达另一个未匹配顶点时找到增广路，沿路交换匹配与非匹配边，匹配数增加一。
3. 搜索遇到同一交错树的两个偶层顶点时，形成奇环。找到它们的公共基点，把这个奇环暂时缩成一个顶点；维护父指针，以便增广时还原环内路径。
4. 本轮找不到增广路时换一个未匹配的起点，直到所有起点都处理完。

奇环除基点外的顶点已被环内匹配配对。经过缩点的交错路径可以沿奇环两侧中奇偶性合适的一侧展开；反之，原图中的增广路径也能在缩图中表示。因此缩花保留增广路的存在性。没有增广路的匹配是最大匹配，结合上面的覆盖等式即可得到答案。

## 实现与复杂度

用字符串映射编号；未出现的军队保留为孤立顶点。程序中的 `Match` 记录匹配对象，`Parent` 记录交错树前驱，`Base` 记录缩花后的基点。每轮搜索重置临时数组，保留当前匹配。

时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(n+m)$ .代号映射另需与输入代号总字节数成正比的空间。