← 返回题目列表

Codeforces · 444/A

A. DZY 热爱物理

中文机器翻译题面 查看原题

DZY 热爱物理,他喜欢计算密度。

几乎所有东西都有密度,甚至是图表。我们将无向图(图的节点和边都有一些值)的密度定义如下:

$$\begin{案例}
\dfrac{v}{e} & (e > 0) \\
0 & (e = 0)
\end{案例}$$

一旦DZY得到了图G,现在他想找到该图的连通诱导子图G',使得G'的密度尽可能大。

图 G(V, E) 的导出子图 G'(V', E') 是满足以下条件的图:

- $$V' \subseteq V$$;
- 边 $$(a,b)\in E^{T}$$ 当且仅当 $$a \in V'、b \in V'$$ 且边 $$(a,b)\in E$$;
- G' 中的边的值与 G 中相应边的值相同,节点的值也是如此。

帮助DZY找到密度最大的诱导子图。请注意,您选择的诱导子图必须是连接的。

输入

第一行包含两个空格分隔的整数 n (1 ≤ n ≤ 500), $$m \left( 0 \leq m \leq \frac{n(n-1)}{2} \right)$$。整数n表示图G的节点数,m表示边数。

第二行包含 n 个空格分隔的整数 xi (1 ≤ xi ≤ 106),其中 xi 表示第 i 个节点的值。考虑图节点的编号从 1 到 n。

接下来的 m 行包含三个空格分隔的整数 ai、bi、ci(1 ≤ ai < bi ≤ n;1 ≤ ci ≤ 103),表示节点 ai 和 bi 之间值为 ci 的边。该图不会包含多条边。

输出

输出一个表示答案的实数,绝对或相对误差最多为 10 - 9。

示例

输入 #1

1 0
1

输出 #1

0.000000000000000

输入 #2

2 1
1 2
1 2 1

输出 #2

3.000000000000000

输入 #3

5 6
13 56 73 98 17
1 2 56
1 3 29
1 4 42
2 3 95
2 4 88
3 4 63

输出 #3

2.965517241379311

注意

在第一个示例中,您只能选择空子图,或者仅包含节点 1 的子图。

在第二个示例中,选择整个图是最佳的。