11286: 【原1286】最大密度子图

author: Cheezer 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1286

Description

给定一个图G(V, E)，请你找出一个它的连通导出子图G'(V', E')，使这个子图的密度最大。若G'中的边数大于0，则其密度为其点权之和除以其边权之和，否则为0。

导出子图G'指满足 \( (a,b) \in E' iff a \in V', b \in V', (a, b) \in E \)的图。

第一行为两个数n和m。

接下来一行，n个数，表示1~n的点权 \( v_i \) 。

接下来m行，每行3个数 \( a_i,b_i,c_i \) ，表示图G中的一条a与b之间的边，边权为 \( c_i \) ，数据保证图中无重边。

30%的数据：\( 1 \le n \le 15 \)

100%的数据：\( 1 \le n \le 500, 1 \le v_i \le 10^6, 1 \le a_i < b_i \le n, 1 \le c_i \le 10^3 \)

一行，即所求最大密度。请输出9位小数。

2 1
1 2
1 2 1

3.000000000

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！