P7831 题解

problem & blog。

妙妙题。单杀了，来写篇题解。

下文中 \(ans_u\) 表示从 \(u\) 点出发的答案。

考虑直接做。发现更新任何一个点，都可能会对一堆点造成影响，\(O(n^2)\) 无法接受。

一些简单的性质：不能进入一个环的 \(ans_u=-1\)。否则，对于 \((u,v,r,p)\)，\(r\) 是最大的 \(r\)，那么只要 \(ans_u\ge r\)，\(u\) 就可以随便走。

这启示我们跑类似于拓扑排序的东西。

• 先跑一遍拓扑，把 \(-1\) 搞出来。
• 按 \(r_i\) 从大到小排序，每次取出这个最大的 \(r\)，如果它没有被转移过，\(ans_u\gets r\)，然后把这条边去掉。
• 去掉后跑拓扑，由于去掉了边，所以一些环就会破掉了，于是把所有能到它的点（也就是建反图后，\(u\) 能到的点）更新 \(ans_u\gets \max\{r_i, ans_v-p_i\}\)，同时把这条边删掉。
• 这里是没有出边就入队。

每一条边显然只与 \((u,v)\) 有关，实际的正确性取决于枚举的顺序。这条边没被删，当且仅当它在一个环里。找到最大的 \(r_i\)，\(u_i\) 想要过掉这条边，确实得有这个限制。如果我能过掉，那我顺着这个环一直走显然正确。所以用类似于倒着反推的方式，一定能得到正确的答案。

实现方面直接建反图。删边直接标记一下就行。

代码，时间复杂度 \(O(m\log m)\)，瓶颈在排序。