警钟长鸣
查看原帖
警钟长鸣
632785
Sakura_Lu楼主2025/1/15 18:00

如果你的 subtask67subtask6,7 出现 WAWA 而其他捆绑点均通过时请来阅读

阅读题解,我们将一个被删去之后会产生孤边的点称为半孤点,一个点被删去的边成为半孤边

我们发现,当我们删去半孤点时,如果一个非半孤点与其形成的边编号小于删去这个半孤点会产生的边中最大的编号,那么要删去那个点

经过我不懈的努力(一整个下午的埋头苦干),我发现,存图方式为邻接表时无法通过,为 vectorvector 时可以通过

这是因为以这种方式删去的点可能是互斥的,即先删去一个非半孤点会导致另一个可以被删去的非半孤点变为不可以这种方式删去的半孤点,最优的策略是按照删去这几个非半孤点产生的半孤边的编号,以从小到大的顺序排序,能删则删

当我们使用 vectorvector 时,正好符合了按编号从小到大的顺序,用邻接表时正好是从大到小的顺序

卡在这个地方的人应该一点就透了,不再赘述,这个题我认为用邻接表做起来更方便一些,所以我的处理方法是额外开了一个数组 ed[]ed[] ,每次加边从 ed[x]ed[x] 加边而不从 head[x]head[x]

2025/1/15 18:00
加载中...