#P2866. 美丽国度

    ID: 1975 传统题 3000ms 512MiB 尝试: 22 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-Tarjan 强连通分量算法最小割建模最大流最小割定理Dinic二分答案定点数十进制舍入

美丽国度

题目描述

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

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

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

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

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

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

输入格式

第一行两个数 nn 和 mm,nn 个城市的标号为 11 到 nn。

第二行 nn 个整数 f1,…,fnf_1,\ldots,f_n,表示各城市的贸易输出额。本站评测数据满足 0≤fi≤1000\le f_i\le100。

接下来 mm 行每行两个数 x,yx,y,表示一条公路从 xx 到 yy,其中 1≤x,y≤n1\le x,y\le n。允许自环和重边,每条公路单独计数。可达关系允许长度为零的路径,城市本身也属于它的互利集合。

输出格式

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

2 2
1 2
1 2
2 1
3.00

数据规模与约定

对于 100%100\%​ 的数据,1≤n≤3001\leq n\leq 300,0≤m≤n20\leq m\leq n^2。