湖底之城

· · 题解

大家猜测一下这个湖是什么湖。

Subtask 1

特殊限制：n\le 100,p\le 20。

直接每个点开始爆搜即可。只要实现的不是太烂，基本上都能通过。

Subtask 2,3

特殊限制：n\le 1000,p\le 100 和 m=1。

观察从每个点开始爆搜的时候，从点 u 到点 v 的距离是不变的。所以，我们可以得到一个结论：在某一个可以做减法的时刻，是否选择做减法，对后面能不能做减法是没有影响的。于是选择贪心法，从 s 中的每个点开始搜索，但是只记录最小答案。时间复杂度 O(nm)。

Subtask 4

特殊限制：p=1。

观察到一个性质：在树上从任意点 $u$ 走到任意点 $v$ 的过程中，经过的点的深度先单调递减，后单调递增。就是说只会有一个向根节点走的过程和一个向叶子节点走的过程。那么就可以两个过程分开考虑了。设 $f_i$ 是第一个过程中走到点 $i$ 的最优解，$g_i$ 是第二个过程中走到 $i$ 的最优解，那么就有 $f_i=\min\{f_v+w,0\},g_i=\min\{g_u+w,f_u+w,0\}$。但是有一个问题，就是我们要防止形如 $v\to u\to v$ 的一个过程，所以我们在转移 $f$ 数组的时候要记录一个次大值，和最大值是从哪个点转移而来。 两个数组的初始值，显然是正无穷，除了 $s$ 中的点初值为 $0$。 ## Subtask 5 特殊限制：树是一条链。 链上显然只有全部向下走和全部向上走两种可能。所以上面记录最小值和次小值的做法在这里不需要了。 但是，上面的 $p=1$ 条件在这里没了。因此我们还需要添加一维：从起点到当前点的距离对 $p$ 取模后得到的值。当且仅当这一维的值是 $0$ 的时候才可以做减法。然后直接转移就行了。 ## Subtask 6 综合上述两个子任务的做法。设 $f_{i,j}$ 是当前在第 $i$ 个点，路径总长对 $p$ 取模得到 $j$ 的最优解。那么首先 $f_{i,j}=\min\{f_{v,j-1}+w\}$。在 $j=0$ 时还有 $f_{i,j}=\min\{f_{i,j},0\}$。注意只有在至少存在一个 $f_{v,p-1}\ne \mathrm{inf}$ 时才可以进行转移。对于 $g$ 的转移类似。然后在转移 $f$ 的时候记录一下次优解即可。 总时间复杂度 $O(np)$，空间复杂度 $O(np)$。可以通过本题。