# 练习 ## CSES 1195 本题有几种做法，这里全部介绍。 ### 方法 1：正反图 + 枚举边 #### 直觉 1. 任意一条最优解路径一定经过一条使用优惠券的边 $(u, v, w)$（表示一条从 $u$ 到 $v$ 的边权为 $w$ 的边）。可以枚举使用优惠券的边，求出当前情况下的最优解，再对所有边对应的最优解求一个最小值。 2. 把最优解路径拆分为三段： $ 1 \leadsto u \text{的最短路} + \left \lfloor \dfrac{w}{2} \right \rfloor + v \leadsto n \text{的最短路} $ 3. 通过预处理最短路，降低时间复杂度 #### 做法 1. 在原图上从起点 $1$ 跑一次 Dijkstra，得到 $ dist1[u] = \text{从 1 到 u 的最短距离} $ 2. 在反图上从起点 $n$ 跑一次 Dijkstra，得到 $ distN[v] = \text{从 v 到 n 的最短距离} $ 3. 只能使用一张优惠券，枚举边 $(u, v, w)$ 作为使用优惠券的边，求出当前情况下的最优解，再对所有边对应的最优解求一个最小值，即答案为 $ \min_{(u\to v,w)\in E} dist1[u] + \left \lfloor \frac{w}{2} \right \rfloor + distN[v] $ #### 时间复杂度 - 两次 Dijkstra（优先队列实现），$O(m \log m)$ - 枚举所有边求解最优解，$O(m)$ 总时间 $O(m \log m)$。 #### 空间复杂度 - 原图和反图的邻接表，$O(n + m)$ - 记录最短路的数组，$O(n)$ - Dijkstra 的优先队列实现中优先队列所占空间，$O(m)$ 总空间 $O(n + m)$。 #### 方法 2：状态图（分层图） 可以建立两层状态图。状态（点）和转移（边）描述如下： - 状态 $(u, 0 / 1)$ 表示当前在点 $u$、是否用过优惠券 - 从 $(u, 0)$ 走到 $(v, 0)$，边权为 $w$，表示不使用优惠券 - 从 $(u, 0)$ 走到 $(v, 0)$，边权为 $\left \lfloor \dfrac{w}{2} \right \rfloor$，表示在原图上的 $u \to v$ 这条边使用优惠券 - 从 $(u, 1)$ 走到 $(v, 1)$，边权为 $w$，表示已经使用完优惠券后正常走 对这 $2n$ 个点跑一遍从 $(1, 0)$ 开始的最短路，答案是 $(n, 1)$ 的最短路。 在实现上有两种方法。 隐式建图：设置数组 $dist[u][0/1]$，然后直接在原图上用 Dijkstra 进行状态转移。对于 Dijkstra 中枚举当前点的出边 $(u \to v, w)$： - 不使用优惠券和已经使用过优惠券，$dist[u][0] + w \to dist[v][0], dist[u][1] + w \to dist[v][1]$ - 在这条边使用优惠券，$dist[u][0] + \left \lfloor \frac{w}{2} \right \rfloor \to dist[v][1]$ 显式建图：建立 $2n$ 个点，对于原图上的每一条边 $(u \to v, w)$，在新图上建立边 $(u \to v, w), (u \to v + n, \left \lfloor \frac{w}{2} \right \rfloor), (u + n \to v + n, w)$。目标改为求新图上点 $1$ 到 $2n$ 的最短路 两种实现方法的时空复杂度一致。 #### 时间复杂度 一共有 $2n$ 个状态（点）、$3m$ 次转移（边），跑一次 Dijkstra，时间 $O(3m \log (3m)) = O(m \log m)$。 #### 空间复杂度 - 显示建图中新图的邻接表，$O(2n + 3m) = O(n + m)$；隐式建图中原图的邻接表，$O(n + m)$ - 记录最短路的数组，$O(2n) = O(n)$ - Dijkstra 的优先队列实现中优先队列所占空间，$O(3m) = O(m)$ 总空间 $O(n + m)$。 ## 洛谷 P4568 状态图（分层图）。 我们可以使用显示建图： - 不使用优惠券，建无向边 $(a + pn \leftrightarrow b + pn, c)$，其中 $0 \le p \le k$ - 使用优惠券，建有向边 $(a + pn \to b + (p + 1)n, c)$，其中 $0 \le p \lt k$ 也可以不建图，直接在原图用 Dijkstra 做状态转移。对于边 $(u \to v, w)$： - 不使用优惠券，$dist[u][p] + w \to dist[v][p]$，其中 $0 \le p \le k$ - 使用优惠券，$dist[u][p] \to dist[u][p + 1]$，其中 $0 \le p \lt k$ 在本题中，隐式建图更加方便。以下时空复杂度分析采用隐式建图方法。 #### 时间复杂度 一共有 $(k + 1)n$ 个状态，每个状态最多两次转移（是否使用优惠券），跑一次 Dijkstra，时间 $O(kn \log (kn))$。 #### 空间复杂度 - 原图的邻接表，$O(n + m)$ - 记录最短路的数组，$O(kn) = O(n)$ - Dijkstra 的优先队列实现中优先队列所占空间，$O(3m) = O(m)$ 总空间 $O(n + m)$。