6866: BZOJ2866:美丽国度

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

从前有个美丽的C国,在C国中,有n个城市,m条单向的公路。对于一个城市u,有一个固定的贸易输出额f。对于两个城市u和v,如果从u有路径到v,且从v有路径到u,则我们称u、v为一对互利城市。对于每一对互利的城市u、v,如果存在一条公路<x,y>,满足u有路径到x,y有路径到v,我们则称这条公路<x,y>为u到v的重要公路。而每一对互利城市u、v,u都会向每一条u到v的重要公路上输送贸易额为f的货物,同样的v也会向每一条v到u的重要公路输送贸易额为f[v]的货物。一个城市最多在一条公路上输送1次货物,换言之,一个城市u对一条公路的贡献,非f即0。对于每一条公路来说,这条公路的重要程度就是这条公路上货物的贸易额的总和。 现在C国的国王想要选出一些城市,建立城市群。一个城市群就是一个城市的集合,这个城市群的繁荣程度为,所有两端点都是这个城市群中的城市的公路,的重要程度和。当然啦,如果就以城市群的繁荣程度来评判一个城市群似乎不太公平,极易导致地方割据的长生。于是乎聪明的C国国王就想到了平均繁荣程度的概念,一个城市群的平均繁荣程度为,这个城市群的繁荣程度与这个城市群城市个数的比值。 现在C国的国王想知道,在他国家里,平均繁荣程度最高的城市群的平均繁荣程度为多少。  


输入格式

第一行两个数n和m,n个城市的标号为1到n。 第二行n个数表示,每个城市的贸易输出额。 接下来m行每行两个数x、y,表示一条公路从x到y。  


输出格式

  一行一个数,表示最大的平均繁荣程度,保留两位小数。  


样例输入

2 2
1 2
1 2
2 1
 

样例输出

3.00
 

提示

对于100%的数据n <= 300,m <= n*n


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: