← 返回题目列表

AtCoder · abc144_f

F. 岔路口

中文机器翻译题面 查看原题

分数: 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