P4745 题解

Peter0701 · 2019-10-28 21:42:54 · 题解

题意

给定一张 n 个点， m 条边的无边权的无向图。有一人从 1 号点出发，可以随机向一个和当前直接相连的点走去，花费 1 的代价；也可以不动，重新随机一个点，也花费 1 的代价。求到达 n 点时的最小总花费。答案四舍五入保留 6 位小数。

解法

根据期望 dp 的一般设计方法，因为只有一个终点，且状态已知（期望花费为 0 ），因此考虑逆推。

自然地，设 f_x 表示点 x 到终点的期望花费。用 E 表示边集， deg_x 表示 x 点的度数，则有 f_x=\frac{ \sum \min \{ f_x,f_y \} }{deg_x}+1 （边 (x,y) 在 E 内）。

那么，对于一个点 x 来说，能对它的期望产生贡献的相邻的点 y 必然有 f_y<f_x 。

一开始不妨令所有的 x 点在计算 \min \{ f_x,f_y \} 时都为 f_x （下文会证明确实只会出现这种情况）。

假设这样的 y 点有 cnt_x 个，则有 f_x=\frac{ \sum f_y}{deg_x}+ \frac{(deg_x-cnt_x) \times f_x}{deg_x}+1=\frac{ \sum f_y}{deg_x}+(1- \frac{cnt_x}{deg_x} ) \times f_x+1 （边 (x,y) 在 E 内且 f_y<f_x ）。

因此，果断求出 \sum f_y （边 (x,y) 在 E 内且 f_y<f_x ），记为 sum_x ，则 f_x=\frac{sum_x}{deg_x}+(1- \frac{cnt_x}{deg_x} ) \times f_x+1 ，化简得 f_x= \frac{deg_x+sum_x}{cnt_x} 。

也就是说，只要相连的 x,y 两点满足 f_y<f_x ，我们就可以利用 f_y 来更新 f_x 的值。

是不是很像堆优化的 dijkstra 的松弛操作呢？时间复杂度与堆优化的 dijkstra 相同，为 O((m+n)logn) 。

trick