致歉
查看原帖
致歉
41476
gyh20楼主2022/1/22 14:37

十分抱歉,这道题的 std 锅了。

主要原因我们用到了一个结论是在某个状态下,假如下一条要被删除边编号是 ii,那么某种最优策略一定是下一步删掉 XiX_iYiY_i 中的一个点。

这个结论看上去很显然,题解中也给出了证明,但遗憾的是,题解中的证明在其中一步出了错。题解中提到假设这种做法不是最优,那么令这种做法第 ii 条边与最优解不同,那么前 i1i-1 条边所覆盖的点集一定已经被选,假如另外多选一个点不会使得可选的边变得不可选,进而不会产生影响。

但实际上这个做法忽略了前 i1i-1 条边覆盖的点集所包含的边集大小 >i1>i-1,也就是说,下一条被删的边已经确定的情况,这个时候是特殊的,就正如 hack 数据那样。

自己把检查的重心放在 O(m2)O(m^2) 的暴力和 O(mlogm)O(m\log m) 的 std 的对拍上面,忽略了这个简单结论的正确性。

再次向大家表示歉意,目前个人不是很清楚是否有正确的做法,将暂时把本题设为隐藏。

2022/1/22 14:37
加载中...