出题: Chielo, 验题: chitanda。
简明题解：奇偶染色 + 二分图最小点覆盖 + Kőnig 定理。
题解#
容易发现，从圆上或圆内任意一整点开始进行奇偶染色，就将原图转化为二分图了（容易从每个点到出发点的曼哈顿距离的奇偶性证明这一点）。
记转化后的二分图为 \(B(V = L \cup R, E)\)，那么问题就变为：
选取若干个点构成点集 \(S \subseteq V\)，使得每条边 \(e \in E\) 都与 \(S\) 中至少一个点相邻。实际就是二分图的最小点覆盖问题。
由 Kőnig 定理，我们就知道了这个 \(S\) 的大小恰好等于完美匹配的大小，并且构造方法也在定理中阐述了。
构造与证明#
QwQ，我还是好好地给出构造方案和证明吧。
构造#
假设已经用匈牙利算法得到了完美匹配的一个方案，从每个 \(L\) 中未匹配的点出发，在不清空时间戳的情况下，搜索增广路，即进行 dfs。正常情况下应该搜不出来新的增广路。那么 \(L\) 中所有的未被访问到、且是匹配点的点集 \(L’\)，和 \(R\) 中所有被访问到的、且是匹配点的点集 \(R’\)，两者的并集就构造出了最小点覆盖 \(S_0\)。
用网络流的说法就是：设 \(E\) 中的边流量为 \(1\)，源点向 \(L\) 的每个点连接流量为 \(1\) 的边，\(R\) 的每个点向汇点连接流量为 \(1\) 的边。获得一个最大流的方案后，在残余网络中从源点出发进行染色。所有源点到 \(L\) 的边跑满并且未被染到的点以及所有 \(R\) 到汇点的边跑满并且被染到的点，构成的集合是一个最小点覆盖 \(S_0\)。这个过程和匈牙利的做法本质是相同的。
证明#
\(|\text{最小点覆盖}| \ge |\text{完美匹配}|\)#
由于完美匹配构成的边集都是互不相邻的，即都没有公共的点，而最小点覆盖又需要把所有边都覆盖到，所以 \(S\) 的大小至少要大于或等于完美匹配的大小。
\(|S_0| = |\text{完美匹配}|\)#
由我们的构造方案知，这等价于证明每条匹配边 \(e=(u,v)\) 的两个点染色情况相同。在残余网络中搜寻的过程中，若 \(u \in L\) 被遍历到，但由于 \(u\) 是匹配点，不是我们遍历过程的起始点，因此它必然是从 \(v\) 那里顺着反向边过来的；而若 \(v \in R\) 被遍历到，那由于这条边是流满的，反向边还有流量，那么 \(u\) 必然也被遍历到。所以，\(u\) 被染色，当且仅当 \(v\) 被染色，逆否命题也成立。
综上，完美匹配中的每条边，两个端点 \(u,v\) 的染色情况是相同的。而我们的构造过程也是从匹配边端点的访问情况进行二选一，所以 \(S_0\) 的大小恰好等于完美匹配的大小。
\(S_0\) 是一个点覆盖#
假设有条边 \(e=(u,v) \in E\), \(u \in L\), \(v \in R\)，未被 \(S_0\) 中的点覆盖。
引理部分：
- 由于 \(S_0\) 是从完美匹配中构造出来的，所以匹配边肯定是被覆盖到的，因此 \(e\) 是非匹配边。
- 而若 \(e\) 是非匹配边，那么两个点必然不能同时是非匹配点，否则这条边可以用来增广，那么先前的匹配就不是完美匹配了。
- 由于 \(e\) 未被覆盖，所以 \(u, v\) 均不在构造的 \(S_0\) 中，这样就可以从 \(u, v\) 的染色情况得到 \(u, v\) 是否是匹配点的信息。
证明部分：
- 假设 \(u, v\) 均未被染到，那么 \(u\) 肯定不是遍历的起点，即 \(u\) 是匹配点，那么 \(u \in S_0\)，这个边是覆盖到的，矛盾；
- 假设 \(u, v\) 均被染到，因为 \(u, v\) 均不在 \(S_0\) 中，所以 \(v\) 只能是非匹配点，由于不能同时是非匹配点，所以 \(u\) 也只能是匹配点，那这两个点同时被染到，不就相当于找到了一条增广路吗，匹配不是完美匹配，矛盾；
- 假设 \(u\) 未被染到，\(v\) 被染到，但 \(u, v\) 均不在 \(S_0\) 中，那这两个点都不能是匹配点，与不能同时是非匹配点矛盾；
- 假设 \(u\) 被染到，\(v\) 未被染到，但 \(e\) 是非匹配边，在残余网络中是有流量的，\(u\) 被染到，接下来肯定会染到 \(v\)，与构造方式矛盾。
综上，\(e=(u,v)\) 不管什么情况，都会有矛盾，所以由反证法，\(e\) 不可能存在，因此所有边都被覆盖到了。
证明总结#
\(S_0\) 是一个大小等于完美匹配的点覆盖，而最小点覆盖的大小是大于或等于完美匹配的大小；因此我们找到了 \(S_0\) 是点覆盖中，大小取到最小值的那个，所以 \(S_0\) 是一个最小点覆盖。
实际，通过上面的构造和证明，很容易发现若 \(u \in L\) 没被染，它肯定是个匹配点，若 \(v \in R\) 被染，如果 \(v\) 是个非匹配点就找到增广路了，所以 \(v\) 也肯定是个匹配点。所以构造的时候可以不需要判是否是匹配点。
比赛结果分析#
当时，出到这一道的时候图论题还不是很多。所以本来这道题，是按图论+定理题+中前期出的，运用到了常见的二分图模型——网格图，以及 Kőnig’s theorem。但是听说 OnlineJudge 支持 SPJ，所以写了一个 SPJ 试了试，结果没想到好多人卡在“方案”这一步了。最后通过率 7/9，都是前排选手在后期AC的（看来卡题意了）……略遗憾。
这个定理常用它的结论，也就是最小点覆盖和完美匹配相等这一点，但实际定理中是有阐述出如何从匹配构造出点覆盖的，所以对定理的学习也应该深入一些（讲给自己）。
评论