ABC335E 分析

__ryp__ · 2024-01-07 08:52:18 · 个人记录

赛时 24 分切了 ABC，看了 D 感觉很恶心就没做，就做开了 E。最开始还以为是个简单的 DP，结果越做越不对劲，有几个坑点：

• 求的是路径的长度，不是权值和
• 求的路径长度要求权值要去重
• 更要命的是，没去重之前路径的最长值不是去重后的最长值

所以一直卡到 9:39 分还在调一个基于集合的屎山 DFS + DP。后来看了一篇题解豁然开朗。

我们可以将权值相同的节点视作一个节点，然后建小权值指大权值的有向图，之后用拓扑求最长路即可。

但是它扛不住这个 hack

4 4
1 2 1 4
1 2 2 3 2 4 3 4

我们的代码输出 0，因为这时点 2 的入度是 2（1 和 3），而 3 是永远访问不到的，故我们就访问不到 4。我们需要改一下，只建能从 1 能访问到的边，即跑一边 DFS 记录，然后重新建边即可。