bzoj#P2866. 美丽国度

美丽国度

题目描述

从前有个美丽的 C 国,在 C 国中,有 nn 个城市,mm 条单向的公路。

对于一个城市 uu,有一个固定的贸易输出额 fuf_u。对于两个城市 uuvv,如果从 uu 有路径到 vv,且从 vv 有路径到 uu,则我们称 u,vu,v 为一对互利城市。

对于每一对互利的城市 u,vu,v​,如果存在一条公路 xyx\to y​,满足 uu​ 有路径到 xx​,yy​ 有路径到 vv​,我们则称这条公路 xyx\to yuuvv 的重要公路。

而每一对互利城市 u,vu,vuu 都会向每一条 uuvv 的重要公路上输送贸易额为 fuf_u 的货物,同样的 vv 也会向每一条 vvuu 的重要公路输送贸易额为 fvf_v 的货物。一个城市最多在一条公路上输送 11 次货物,换言之,一个城市 uu 对一条公路的贡献,非 fuf_u00。对于每一条公路来说,这条公路的重要程度就是这条公路上货物的贸易额的总和。

现在 C 国的国王想要选出一些城市,建立城市群。一个城市群就是一个城市的集合,这个城市群的繁荣程度为,所有两端点都是这个城市群中的城市的公路,的重要程度和。当然啦,如果就以城市群的繁荣程度来评判一个城市群似乎不太公平,极易导致地方割据的长生。于是乎聪明的 C 国国王就想到了平均繁荣程度的概念,一个城市群的平均繁荣程度为,这个城市群的繁荣程度与这个城市群城市个数的比值。

现在 C 国的国王想知道,在他国家里,平均繁荣程度最高的城市群的平均繁荣程度为多少。

输入格式

第一行两个数 nnmmnn 个城市的标号为 11nn

第二行 nn 个数表示,每个城市的贸易输出额。

接下来 mm 行每行两个数 x,yx,y,表示一条公路从 xxyy

输出格式

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

2 2
1 2
1 2
2 1
3.00

数据规模与约定

对于 100%100\%​ 的数据,1n3001\leq n\leq 3000mn20\leq m\leq n^2