← 返回题目列表

Codeforces · 208/C

C. 警察局

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

Berland 道路网由 n 个城市和 m 条双向道路组成。城市编号从1到n,其中主都城市编号为n,文化首都编号为1。道路网络的建立使得从任何一个城市都可以通过道路到达任何一个城市。在每条道路上向任何方向移动都需要相同的时间。

Berland的所有居民都是非常懒惰的人,因此当他们想要从城市v到城市u时,他们总是选择最短路线之一(无论哪一条)。

Berland 政府希望使该国的道路网络更加安全。为此,它将在一个城市设立一个警察局。警察局有一个相当奇怪的特性:当一名伯兰公民沿着一端有警察局的道路行驶时,该公民驾驶得更加小心,因此所有此类道路都被认为是安全的。这些道路的两端与警察局所在的城市不同,很危险。

现在政府想知道警察局应该放在哪里,以便从文化之都到主首都的所有最短路径的平均安全道路数量取最大值。

输入

第一输入行包含两个整数 n 和 m (2 ≤ n ≤ 100, $$n-1 \leq m \leq \frac{n(n-1)}{2}$$) — 相应地,Berland 的城市数量和道路数量。接下来的 m 行包含整数对 vi, ui (1 ≤ vi, ui ≤ n, vi ≠ ui) — 第 i 条道路连接的城市数量。一行上的数字由空格分隔。

保证每对城市连接的道路不超过一条,并且可以沿着 Berland 道路从任何城市到达任何其他城市。

输出

打印从文化首都到主要文化首都的所有最短路径中安全道路平均数量的最大可能值。如果答案的绝对或相对不准确度不超过 10 - 6,则答案将被视为有效。

示例

输入 #1

4 4
1 2
2 4
1 3
3 4

输出 #1

1.000000000000

输入 #2

11 14
1 2
1 3
2 4
3 4
4 5
4 6
5 11
6 11
1 8
8 9
9 7
11 7
1 10
10 4

输出 #2

1.714285714286

注意

在第一个示例中,您可以在其中一个首都设立一个警察局,那么每条路径将只有一条安全道路。如果我们把车站设在首都之外,那么平均安全道路数也会使得 $${ \frac { 0 \cdot 1 + 2 \cdot 1 } { 2 } } = 1$$。

在第二个样本中,如果我们将站点放在城市 4 中,我们可以获得最大寻求值,那么 6 条路径将分别有 2 条安全道路,而 1 条路径将有 0 条安全道路,因此答案将等于 $$\frac{6 \cdot 2 + 1 \cdot 0}{7} = \frac{12}{7}$$。