← 返回题目列表

Codeforces · 1874/C

C. 水母和EVA

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

怪物再次入侵城镇!明日香邀请她的好朋友水母一起驾驶 EVA。

城镇中有 $$$n$$$ 个城市。所有怪物都在城市$$$n$$$。水母和明日香目前在城市$$$1$$$,需要移动到城市$$$n$$$来击败怪物。

有 $$$m$$$ 条道路。第 $$$i$$$ 条道路允许人们从城市 $$$a_i$$$ 前往城市 $$$b_i$$$。所有的道路都是有方向的。也就是说,人们无法使用第 $$$i$$$ 条道路从城市 $$$b_i$$$ 前往 $$$a_i$$$。有趣的是,所有道路都满足$$$a_i<b_i$$$。

驾驶EVA需要两个人一起工作。不过,明日香和水母之前并没有一起进行过任何训练。

假设 EVA 目前位于城市 $$$u$$$。水母和明日香都会选择一条从 $$$u$$$ 城市开始的未受破坏的道路。假设 Jellyfish 和 Asuka 选择分别以城市 $$$v_1$$$ 和 $$$v_2$$$ 为终点的道路。如果$$$v_1 = v_2$$$,则EVA成功移动到城市$$$v_1$$$。否则,EVA 会留在城市 $$$u$$$ 并且他们选择的两条道路都将被摧毁。

EVA 当前可能位于城市 $$$u$$$ ($$$u \neq n$$$) 并且没有从城市 $$$u$$$ 开始的未毁坏道路。那样的话,任务就会失败。否则,如果最终到达城市$$$n$$$,则视为任务成功。

每次选择道路时,水母都知道明日香会随机选择一条道路。现在,水母想知道,如果她选择最佳道路,任务成功的最大概率是多少。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 2000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数,$$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 5000$$$, $$$0 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$$$) — 城市数量和道路数量。

在每个测试用例的以下 $$$m$$$ 行中,每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a < b \leq n$$$) - 表示从城市 $$$a$$$ 到城市 $$$b$$$ 的道路。

保证对于每个测试用例,每条路最多出现一次。

保证所有测试用例的 $$$n$$$ 总和不会超过 $$$5000$$$,并且所有测试用例的 $$$m$$$ 总和不会超过 $$$2 \cdot 10^5$$$。

输出

输出如果 Jellyfish 选择最佳道路,任务成功的最大概率。

如果绝对或相对误差不超过 $$$10^{-9}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$$$,则认为您的答案是正确的。

示例

输入 #1

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

输出 #1

0.500000000000
0.625000000000
0.491666666667

注意

在第一个测试用例中,Jellyfish 将选择 $$$v_1=3$$$,Asuka 将选择 $$$v_2=2$$$(可能性为 $$$0.5$$$)和 $$$v_2=3$$$(可能性为 $$$0.5$$$)。该任务被视为成功,可能性为 $$$0.5$$$。