分数: 600 点
问题陈述
有一个洞穴,由 N 房间和 M 单向通道。房间有编号 1 通过 N.
高桥现在在房间里 1和房间 N 有出口。的 i第通道连接房间 s_i 和房间 t_i (s_i < t_i)并且只能从 Room 方向遍历 s_i 到房间 t_i。据了解,对于除 Room 之外的每个房间 N,至少有一条通道从那个房间出去。
高桥将从洞穴中逃脱。每次他到达一个房间(假设他已经到达房间 1 开头),他会从那个房间出去的通道中统一随机选择一条通道并走那条通道。
高桥的朋友青木可以在高桥离开房间之前封锁其中一条通道(或不执行任何操作) 1。但是,不允许堵塞通道,这样高桥就有可能无法到达房间 N.
让 E 是 Takahashi 在到达 Room 之前预计经过的次数 N。求出 的值 E 当青木做出最小化的选择时 E.
约束
- 2 \leq N \leq 600
- N-1 \leq M \leq \frac{N(N-1)}{2}
- s_i < t_i
- If i != j, (s_i, t_i) \neq (s_j, t_j). (日本标准时间 21:23 添加)
- 对于每个 v = 1, 2, ..., N-1,存在 i 这样 v = s_i.
输入
输入由标准输入按以下格式给出:
N M s_1 t_1 : s_M t_M
输出
打印以下值 E 当青木做出最小化的选择时 E。 当判断者输出的绝对或相对误差最多为时,您的输出将被判断为正确 10^{-6}.
示例输入 1
4 6 1 4 2 3 1 3 1 2 3 4 2 4
示例输出 1
1.5000000000
如果青木挡住了房间的通道 1 到房间 2,高桥会沿着这条路走 1 → 3 → 4 有概率 \frac{1}{2} 和 1 → 4 有概率 \frac{1}{2}. E = 1.5 这里,这是最小可能值 E.
示例输入 2
3 2 1 2 2 3
示例输出 2
2.0000000000
封锁任何一条通道都会使高桥无法到达房间 N,所以青木无法阻挡通道。
示例输入 3
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
3.0133333333