Fork in the Road

题目描述

有一个由 $N$ 个房间和 $M$ 条单向通道组成的洞穴。房间编号为 $1$ 到 $N$。 Takahashi 现在在房间 $1$，房间 $N$ 有出口。第 $i$ 条通道连接房间 $s_i$ 和房间 $t_i$（$s_i$ < $t_i$），且只能按从房间 $s_i$ 到房间 $t_i$ 的方向通过。已知对于除房间 $N$ 之外的每个房间，至少存在一条从该房间出发的通道。 Takahashi 将从洞穴中逃出。每次他到达一个房间（假设一开始他已到达房间 $1$），他会从该房间出发的通道中均匀随机地选择一条并通过该通道。 Takahashi 的朋友 Aoki 可以在 Takahashi 离开房间 $1$ 之前阻塞一条通道（或者什么也不做）。但是，不允许阻塞一条使得 Takahashi 可能无法到达房间 $N$ 的通道。 设 $E$ 为 Takahashi 到达房间 $N$ 之前所走通道数的期望值。当 Aoki 做出使 $E$ 最小化的选择时，求 $E$ 的值。

输入格式

输入由标准输入按以下格式提供： $N$ $M$ $s_1$ $t_1$ : $s_M$ $t_M$

输出格式

当 Aoki 做出使 $E$ 最小化的选择时，输出 $E$ 的值。 当你的输出与裁判输出的绝对误差或相对误差不超过 $10^{-6}$ 时，将被视为正确。

4 6
1 4
2 3
1 3
1 2
3 4
2 4

1.5000000000

3 2
1 2
2 3

2.0000000000

10 33
3 7
5 10
8 9
1 10
4 6
2 5
1 7
6 10
1 4
1 3
8 10
1 5
2 6
6 9
5 6
5 8
3 6
4 8
2 7
2 9
6 7
1 2
5 9
6 8
9 10
3 9
7 8
4 5
2 10
5 7
3 5
4 7
4 9

3.0133333333

提示

$2 \leq N \leq 600$ $N-1 \leq M \leq \frac{N(N-1)}{2}$ s_i &lt; t_i If $i != j$, $(s_i, t_i) \neq (s_j, t_j)$. (Added 21:23 JST) 对于每个 $v = 1, 2, ..., N-1$，存在某个 $i$ 使得 $v = s_i$。如果 Aoki 阻塞了从房间 $1$ 到房间 $2$ 的通道，Takahashi 将以概率 $\frac{1}{2}$ 沿路径 $1$ → $3$ → $4$，以概率 $\frac{1}{2}$ 沿路径 $1$ → $4$。此时 $E = 1.5$，这是 $E$ 的最小可能值。
阻塞任意一条通道都会使 Takahashi 无法到达房间 $N$，因此 Aoki 无法阻塞任何通道。

标签: AtCoder|abc144F

来源

AtCoder|abc144F