「JOI 2014 Final」飞天鼠 题解

问题分析

飞天鼠 JOI 君需要在树之间飞行，飞行过程中高度会下降，还可以在树上爬升或下降。我们需要找到从起点（树 $1$ 高度 $X$）到终点（树 $N$ 顶端）的最短时间。

关键约束：

• 飞行时间 $t$ 秒，高度下降 $t$ 米
• 飞行后高度必须在 $[0, H_{\text{目标}}]$ 范围内
• 爬升/下降 $1$ 米需要 $1$ 秒

核心思路

1. 状态设计与最短路建模

我们使用 Dijkstra 算法求解最短时间，但需要巧妙设计状态。

定义 $dis[u]$ 表示到达树 $u$ 时，为了能够继续飞行所需要额外爬升的最小总时间。

为什么这样设计？

• 飞行时高度会下降，可能需要在当前树爬升以保证能飞到下一棵树
• 这个定义包含了所有必要的调整时间

2. 状态转移分析

从树 $u$ 飞到树 $v$ 需要时间 $w$：

飞行可行性条件：当前高度必须满足：

• 飞行后高度 $\geq 0$：$h_u \geq w$（已在建图时处理）
• 飞行后高度 $\leq H_v$：飞行前高度 $- w \leq H_v$

关键观察：如果到达 $u$ 时高度不够，需要先爬升。飞行到 $v$ 后，如果高度低于 $X - dis[v]$ 的理想高度，还需要在 $v$ 处爬升。

状态转移方程：

$$dis[v] = \max(X - H_v, dis[u] + w)$$

解释：

• $X - H_v$：如果目标树 $v$ 较矮，需要提前降低飞行高度
• $dis[u] + w$：继承之前的调整时间加上飞行时间

3. 建图策略

只建立可行的飞行边：

if (w <= h[u]) g[u].emplace_back(v, w);  // 从u飞到v可行
if (w <= h[v]) g[v].emplace_back(u, w);  // 从v飞到u可行

4. 最终答案计算

到达树 $N$ 后，还需要爬到顶端：

$$answer = dis[n] + H_n - (X - dis[n])$$

简化后：

$$answer = 2 \times dis[n] + H_n - X$$

算法正确性证明

1. 最优子结构

$dis[u]$ 确实表示到达树 $u$ 时所需的最小调整时间：

• 包含了所有为了满足飞行约束而进行的爬升
• 通过 Dijkstra 可以保证找到全局最优解

2. 状态转移正确性

对于边 $(u, v, w)$：

• 如果 $H_v$ 较小，必须提前在之前的树上降低飞行高度
• 如果之前调整时间较长，需要继续累积
• $\max$ 操作确保满足所有约束条件

3. 最终答案正确性

从 $dis[n]$ 恢复到实际时间：

• $dis[n]$ 是额外爬升时间
• 还需要从当前高度爬到树顶：$H_n - (X - dis[n])$
• 总时间 = 调整时间 + 最后爬升时间

复杂度分析

• 建图：$O(M)$
• Dijkstra：$O((N+M)\log N)$
• 总复杂度：$O((N+M)\log N)$

对于 $N \leq 10^5, M \leq 3\times 10^5$ 可以接受。

示例验证

样例 1

输入：

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

执行过程：

1. 从树1高度0出发，需要爬升到足够高度
2. 通过 Dijkstra 计算最小调整时间
3. 最终答案：$110$

路径验证：

• 树1爬升50米：时间50
• 1→2飞行：时间10，高度40→30
• 2→4飞行：时间20，高度30→10
• 4→5飞行：时间20，高度10→-10（不可行！说明需要调整）
• 实际需要提前爬升，最终时间110合理

样例 2

2 1 0
1
1
1 2 100

输出：-1（飞行时间100秒，但树高只有1米，无法飞行）

样例 3

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

输出：100（需要适当调整飞行高度）

总结

本题的难点在于：

1. 飞行高度约束的处理
2. 爬升时间与飞行时间的统筹优化
3. 状态设计的巧妙性：用调整时间来统一处理所有约束

通过将问题转化为带约束的最短路问题，并使用 Dijkstra 算法求解，我们能够在合理时间内找到最优解。