← 返回题目列表

AtCoder · indeednow_2015_finala_e

E. 页面排名

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

問題文

一些公司有 有 n 名员工。
在这家公司,座位排成一条直线,员工编号从该直线的末端开始按顺序分配。
该公司使用下述方法来衡量其员工的绩效。

首先,所有员工向公司提交一份他们认为优秀的员工名单。 第
i 位员工提交的列表 N(i) 。
我对坐在远处的员工不太了解,所以N(i) 座位是桌子。 10 分居多个地点的员工不包括在内。
(任何 关于 x \in N(i) 关于 |i - x| < 10 成立)
一旦你收集了每个人的列表,就构建一个图,以员工为顶点,以你认为良好的关系为有向边。
然后,让该图上的 Page Rank 为该员工的能力。 第
i 位员工的页面排名为 认为第 PR(i)、i 个员工优秀的员工集合是 M(i) ,Page Rank 满足以下条件表达式。

你的工作是编写一个程序来查找该公司的页面排名。


入力

输入按以下格式给出。

n m
a_1 b_1
...
a_m b_m
  • 1 行是一个表示员工人数的整数。 n (1 \leq n \leq 10{,}000),一个整数,表示一名员工认为另一名员工是上级的关系数量。 给出 m (1 \leq m \leq 10{,}000)。
  • 继续 m 行包含 一个整数,表示第2 整数 a_i, b_i (1 \leq a_i, b_i \leq n, |a_i - b_i| < 10),即 第 a_i 位员工是 b 表示您认为该员工非常优秀。

出力

在一行中输出每个员工的页面排名值。

如果相对或绝对误差为 10^{-6} 如果答案如下,则视为正确。


入力例1

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

出力例1

1
1
1

入力例2

3 4
1 2
1 3
2 1
3 1

出力例2

1.473684210526316
0.7631578947368423
0.7631578947368423

在这种情况下 3 名员工。
1 位员工是 2 与第 名员工 我认为 3 员工非常优秀。
2 位员工是 1 员工非常优秀。
3 位员工是 1 员工非常优秀。
因此,每个员工的页面排名满足以下所有条件。
PR(1) = 0.1 + 0.9 (\frac{PR(2)}{1} + \frac{PR(3)}{1})
PR(2) = 0.1 + 0.9 (\frac{PR(1)}{2})
PR(3) = 0.1 + 0.9 (\frac{PR(1)}{2})