問題文
一些公司有
有 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})