给定一个 $n$ 个点, $m$ 条边的无向图。聪聪开始的时候在 S
,可可在节点 T
处。以后的每个时间单位,可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M
相邻,它们分别是景点 R
、 景点 S
,……,景点 Q
,在时刻 $i$ 可可处在景点 M
,则在 $i+1$ 时刻,可可有 $\frac{1}{1+P}$ 的可能在景点 R
,有 $\frac{1}{1+P}$ 的可能在景点 S
,……,有 $\frac{1}{1+P}$ 的可能在景点 Q
,还有 $\frac{1}{1+P}$ 的可能停在景点 M
。
当聪聪在景点 C
时,她会选一个更靠近可可的景点,如果这样的景点有多个,她会选一个标号最小的景点。如果走完第一次移动以后仍然没吃到可可,她还可以在本段时间内再向可可进行一次移动。
在每个时间单位,假设聪聪先走,可可后走。在某一时刻,若聪聪和可可位于同一个景点,则可怜的可可就被吃掉了。
请求出平均情况下,聪聪用几个时间单位就可能吃到可可。
链接
题解
有趣的期望dp。
我们注意到,如果我们知道可可和聪聪的位置,那么聪聪的两次移动我们都是唯一的。
所以我们用 $n$ 次 $\text{bfs}$ 处理出所有点对间的最短路,然后针对 $n$ 个可可可能在的点,对每个节点进行一次遍历(边),找到最近的出度。以上两个过程都是 $O(n^2)$ 的。
现在我们就可以进行转移了。
设 $dp[u][v]$ 为聪聪在 $u$ ,可可在 $v$ 时的期望步数,然后转移即可。注意到我们需要遍历 $v$ 这个点对应的所有的边,但是无向图的话,所有的边会被遍历两遍,所以对于每个 $v$ ,转移是 $O(n)$ 的,然后转移的复杂度也是 $O(n^2)$ 。
代码
1 |
|