AGC072E

lsj2009 · 2025-09-30 21:30:00 · 题解

帅爆了这个题。

二分答案，初始有 x 的钱，转换为判定性问题。不妨先考虑链的情况，一个结论是，每次将里程换成钱时要么全部换完，要么换到的钱能恰好使用到下一次兑换；否则考虑调整，设两次相邻的兑换分别在 x,y，且在 x 处既没有把里程用尽，到 y 时钱也没有用完，则必然可以取一个 \varepsilon>0，将 x 处兑换的里程数增加/减小 \varepsilon，必有一者更优。

将每个点细拆成到达和离开时刻，则在每个兑换点上，要么其离开时刻里程为 0，要么在下一个兑换点的到达时刻钱为 0。离开时刻里程为 0 的兑换点称为 A 类特殊点，将到达时刻钱为 0 的点称为 B 类特殊点，则相邻两特殊点间至多隔了一个兑换点，那一个兑换点的情况这仅在两特殊点分别为 A、B 时产生。则令 f_i,g_i 分别为 i 作为 A/B 类特殊点时，离开时最多拥有多少钱/里程；转移考察 (i,j) 为 \{\tt A,B\}^2 的四种情况。

将判定性问题的解法拓展到一般图，显然两交换点间肯定走关于钱的最短路，确定所有兑换点后直接退化到链的情况，故上述所有结论仍然成立！记 d_{u,v} 为 (u,v) 间钱最短路长度，这里给出详细的转移：

使用 Bellman-Ford 模拟上述过程，松弛一个点再转移复杂度为 \mathcal{O}(n^2)。由于成环必然不优，故松弛总轮数不超过 n 次，总复杂度为 \mathcal{O}(n^4\log{V})。

注意到最终答案下，f_n 的值固定为 0，将上述 dp 倒序（并非转置原理，这里不是简单的线性变换），记 f_u,g_u 为 u 作为 A/B 类点，想要到达 n 得最少有的钱/里程，转移即对以上的 dp 解不等式，得：

如此可以去掉二分，直接求解。但复杂度是 \mathcal{O}(n^4) 仍然无法接受。

一个性质是，在旅行过程中，钱 + 里程 \times F 的值不增。走过一段路时该值不变，进行兑换时由于 R_*<F 故该值减少。在上述恰好相反的 dp 过程中，将 f_u/g_u 分别赋权值 f_u,g_u\times F，每次取出权值最小的，拿他取松弛其余点，则按照该顺序，一个被取出过的点不会再被其他点松弛（将 f_u,g_u 即 1\to u 的最终状态为 (f_u,0) 和 (0,g_u) 的路径）！这相当于一个 dijkstra 的过程。复杂度降至 \mathcal{O}(n^3)。