#P2164. [SHOI2007] 交通网络

[SHOI2007] 交通网络

题目描述

著名的城市交通规划师L.Serenade为OItown的各个城堡之间设计了一套的地铁交通网络。每一条地铁线路都用来双向连通两个城堡。因为是建在地下的不同深度,所以这些地铁线路是可以“交叉”的。

OItown的居民们的生活和工作都在不同的城堡中进行,于是,每个OItown的居民都要在每天早晨从家出发,乘地铁去工作,当然地铁换乘是允许的。不过每个居民都会选择换乘次数最少的乘车方式。如果有多种乘车方式,这些乘车方式所需要的换乘次数一样,那么居民每天都会等概率的随机选择其中一种。

现在L.Serenade想请你为他计算出,每天每条地铁线路在早晨的平均客流量。他会告诉你,每个居民的家和工作地址,还有他设计的地铁交通网络的全部信息。

当然L.Serenade保证,交通网络能把城市连为一体,而且任意两个城堡之间的最优乘车方式(即换成次数最少的)不超过2^63-1种。

输入格式

输入文件的第一行有两个整数n、m,分别表示OItown里的城堡数(这些城堡用1.2.3...n标号)和地铁线路的数量。

接下去m行,每行包含两个整数,x、y,表示这两个城堡之间有一条地铁线路。注意,两个城堡之间最多只有一条地铁线路,且每条地铁线路只被输入文件描述一次。

最后的n行,每行有n个整数。

第i行的第j个非负整数Ci,j表示每天早晨有Ci,j个OItown的居民要从i城堡去j城堡。输入数据保证Ci,i=0。

输出格式

输出文件有m行,每行依次表示每条地铁线路每天早晨的平均客流。精确到小数点后一位。整数也应输出一位小数,例如1应输出为1.0。

6 7
1 2
1 3
2 4
2 5
3 5
4 6
5 6
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0.7
0.3
0.3
0.3
0.3
0.3
0.7

提示

样例说明:从城堡1到城堡六的使得换乘次数最少的乘车方式共有3种:1-2-4-6;1-2-5-6;1-3-5-6。所以每个人都有1/3的概率选择这其中的每一种。

N< = 300

M< = N*(N-1) div 2

0< = C(i,j) < = 100