#1021. 2025. [SHOI2009] 交通网络

2025. [SHOI2009] 交通网络

#2025. [SHOI2009] 交通网络

题目描述

著名的城市交通规划师L.Serenade为OItown的各个城堡之间设计了一套的地铁交通网络。每一条地铁线路都用来双向连通两个城堡。因为是建在地下的不同深度,所以这些地铁线路是可以"交叉"的。 OItown的居民们的生活和工作都在不同的城堡中进行,于是,每个OItown的居民都要在每天早晨从家出发,乘地铁去工作,当然地铁换乘是允许的。不过每个居民都会选择换乘次数最少的乘车方式。如果有多种乘车方式,这些乘车方式所需要的换乘次数一样,那么居民每天都会等概率的随机选择其中一种。现在L.Serenade想请你为他计算出,每天每条地铁线路在早晨的平均客流量。他会告诉你,每个居民的家和工作地址,还有他设计的地铁交通网络的全部信息。当然L.Serenade保证,交通网络能把城市连为一体,而且任意两个城堡之间的最优乘车方式(即换成次数最少的)不超过263-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.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