神经突击车：题解¶
解法比较¶
出题人解法把可以成对处理的单位连边，求一般图最大匹配，并以单位数减匹配数得到答案。匹配边对应互不冲突的两单位分组；反过来，任何分组中的双单位组构成匹配，因此两种最优目标等价。出题人实现使用带花树处理奇环，下文解释这一归约及收缩、增广的说明。
使用邻接矩阵时，时间为 \(O(n^3)\) ，空间为 \(O(n^2)\) .Codex（GPT-6）负责数组、队列的实现与算法说明。
建模¶
把军队看作顶点，允许制造冲突的关系看作无向边。一次行动可以覆盖一条边的两个端点，或单独覆盖一个顶点。设一般图的最大匹配大小为 \(\nu\) ，答案为
最大匹配的每条边用一次行动，剩余 \(n-2\nu\) 个顶点各用一次，总计 \(n-\nu\) .
反过来，在任意覆盖方案中不断删除多余行动，得到一个不能再删的方案。单点行动不能与其他行动共用顶点；边组成的每个非平凡连通分量都是星形：若某条边两端都还连着别的边，该边就可删除。每个星形任选一条边，得到一个匹配。一个有 \(v\) 个顶点的星形用了 \(v-1\) 次行动，单点用了 \(1\) 次，因此若剩余行动数为 \(k\) ，这个匹配有 \(n-k\) 条边。于是 \(n-k\le\nu\) ，任何方案都不可能优于 \(n-\nu\) .
一般图最大匹配¶
关系图可能含奇环，不能直接套用二分图匹配。参考程序使用 Edmonds 缩花算法：
- 从一个未匹配顶点出发，按“非匹配边、匹配边”交替扩展交错树。
- 到达另一个未匹配顶点时找到增广路，沿路交换匹配与非匹配边，匹配数增加一。
- 搜索遇到同一交错树的两个偶层顶点时，形成奇环。找到它们的公共基点，把这个奇环暂时缩成一个顶点；维护父指针，以便增广时还原环内路径。
- 本轮找不到增广路时换一个未匹配的起点，直到所有起点都处理完。
奇环除基点外的顶点已被环内匹配配对。经过缩点的交错路径可以沿奇环两侧中奇偶性合适的一侧展开；反之，原图中的增广路径也能在缩图中表示。因此缩花保留增广路的存在性。没有增广路的匹配是最大匹配，结合上面的覆盖等式即可得到答案。
实现与复杂度¶
用字符串映射编号；未出现的军队保留为孤立顶点。程序中的 Match 记录匹配对象，Parent 记录交错树前驱，Base 记录缩花后的基点。每轮搜索重置临时数组，保留当前匹配。
时间复杂度为 \(O(n^3)\) ，空间复杂度为 \(O(n+m)\) .代号映射另需与输入代号总字节数成正比的空间。