bzoj#P2866. 美丽国度
美丽国度
题目描述
从前有个美丽的 C 国,在 C 国中,有 个城市, 条单向的公路。
对于一个城市 ,有一个固定的贸易输出额 。对于两个城市 和 ,如果从 有路径到 ,且从 有路径到 ,则我们称 为一对互利城市。
对于每一对互利的城市 ,如果存在一条公路 ,满足 有路径到 , 有路径到 ,我们则称这条公路 为 到 的重要公路。
而每一对互利城市 , 都会向每一条 到 的重要公路上输送贸易额为 的货物,同样的 也会向每一条 到 的重要公路输送贸易额为 的货物。一个城市最多在一条公路上输送 次货物,换言之,一个城市 对一条公路的贡献,非 即 。对于每一条公路来说,这条公路的重要程度就是这条公路上货物的贸易额的总和。
现在 C 国的国王想要选出一些城市,建立城市群。一个城市群就是一个城市的集合,这个城市群的繁荣程度为,所有两端点都是这个城市群中的城市的公路,的重要程度和。当然啦,如果就以城市群的繁荣程度来评判一个城市群似乎不太公平,极易导致地方割据的长生。于是乎聪明的 C 国国王就想到了平均繁荣程度的概念,一个城市群的平均繁荣程度为,这个城市群的繁荣程度与这个城市群城市个数的比值。
现在 C 国的国王想知道,在他国家里,平均繁荣程度最高的城市群的平均繁荣程度为多少。
输入格式
第一行两个数 和 , 个城市的标号为 到 。
第二行 个数表示,每个城市的贸易输出额。
接下来 行每行两个数 ,表示一条公路从 到 。
输出格式
一行一个数,表示最大的平均繁荣程度,保留两位小数。
2 2
1 2
1 2
2 1
3.00
数据规模与约定
对于 的数据,,。