[ABC368E] Train Delay 题解

前言

笑点解析：

思路

一种很新的建图 trick，看完题解你会发现这题的思想和 [ABC232G] Modulo Shortest Path 一模一样。

先想缩小数据范围怎么做。题意相当于一堆形如 $X_i+(T_i-S_j)\leq X_j$ 的不等式，给定 $X_1$ ，要求最小的一组解。如果点数 $m$ 缩小到 $500$ ，这就是一个差分约束跑最长路的经典问题，直接暴力从每个 $i$ 向 $j$ 连边建图跑最长路然后输出答案即可，边数为 $m^2$ 级别，但有一个很好的性质就是题目保证 $T_i\leq S_j$ ，差分约束边权全部为非正值，可以不用跑 spfa，使用复杂度为 $\mathcal{O}(m^2\log m)$ 的 Dijkstra 求解即可。关于跑最长路能最小化解的正确性不再赘述，感性理解一下最短路算法的松弛过程即可。

我们发现这个做法的瓶颈主要在于图上的边数，如果能把边数缩小到 $\mathcal{O}(m)$ 级别就好了。观察连边过程，我们发现如果将所有 $A_j$ 相等的 $j$ 放在一起按 $S_j$ 排序，那么每次从 $i$ 向 $j$ 连边都是在 $A_j=B_i$ 的所有 $j$ 中挑一段后缀连边。这启示我们使用后缀和优化建图。具体的，在图上新建 $m$ 个虚点，对于每一堆 $A_j$ 相等的 $j$ ，都连上 $(j+m,j,-S_j)$ 和 $(j+m,j+m+1,0)$ 两条有向边，这样对于每个 $i$ 就只用二分最小的满足 $S_j\geq T_i$ 的 $j$ ，连边 $(i,j+m,T_i)$ 即可。

但是问题还没有解决。刚刚的优化建图方式边数为 $\mathcal{O}(m)$ ，但边权存在正负两种值，只能跑复杂度 $m^2$ 的 spfa。由于跑的是最长路，考虑怎么把边权全部转化为负值，这样就可以在全负权图上跑 Dijkstra 了。挖掘“后缀和优化建图”的性质，我们发现一件神奇的事情：如果将所有 $(j+m,j+m+1)$ 的权值改为 $S_j$ 的差分，由于差分的后缀和就是原序列，我们就可以直接凑出每个 $S_j$ ！把边权修改为下图的形式，由于 $S_j$ 从小到大排序，且保证 $T_i\leq S_j$ ，现在图上的边权已经全为负数了。