十分抱歉,这道题的 std 锅了。
主要原因我们用到了一个结论是在某个状态下,假如下一条要被删除边编号是 i,那么某种最优策略一定是下一步删掉 Xi 和 Yi 中的一个点。
这个结论看上去很显然,题解中也给出了证明,但遗憾的是,题解中的证明在其中一步出了错。题解中提到假设这种做法不是最优,那么令这种做法第 i 条边与最优解不同,那么前 i−1 条边所覆盖的点集一定已经被选,假如另外多选一个点不会使得可选的边变得不可选,进而不会产生影响。
但实际上这个做法忽略了前 i−1 条边覆盖的点集所包含的边集大小 >i−1,也就是说,下一条被删的边已经确定的情况,这个时候是特殊的,就正如 hack 数据那样。
自己把检查的重心放在 O(m2) 的暴力和 O(mlogm) 的 std 的对拍上面,忽略了这个简单结论的正确性。
再次向大家表示歉意,目前个人不是很清楚是否有正确的做法,将暂时把本题设为隐藏。