DZY Loves Physics

题意翻译

题目大意：给定一个无向图，定义一个图的联通导出子图的密度为其点权之和除以边权之和。（注：边权之和为零的图密度为零）求该图的联通导出子图的最大密度。一个图的导出子图是指，选取一个顶点集，以两端点均在该顶点集中的边的全体为边集的子图。 输入格式：第一行两个整数n (1<=n<=500) ,m(0<=m<=n(n-1)/2)，分别表示图的节点数和边数。第二行n个整数xi（1<=xi<=1000000）表示第i个点的权值。后m行每行三个整数ai,bi,ci，(1<=ai,bi<=n;1<=ci<=1000)表示从ai到bi有一条权值为ci的无向边。数据保证无重边。 输出：一个浮点数，表示该图的联通导出子图密度的最大值，保留小数点后15位。如果你的答案和标准答案相差不超过10e-9，则被认为是正确的。

题目描述

DZY loves Physics, and he enjoys calculating density. Almost everything has density, even a graph. We define the density of a non-directed graph (nodes and edges of the graph have some values) as follows:  where $ v $ is the sum of the values of the nodes, $ e $ is the sum of the values of the edges.Once DZY got a graph $ G $ , now he wants to find a connected induced subgraph $ G' $ of the graph, such that the density of $ G' $ is as large as possible. An induced subgraph $ G'(V',E') $ of a graph $ G(V,E) $ is a graph that satisfies: - ; - edge  if and only if , and edge ; - the value of an edge in $ G' $ is the same as the value of the corresponding edge in $ G $ , so as the value of a node. Help DZY to find the induced subgraph with maximum density. Note that the induced subgraph you choose must be connected. 

输入输出格式

输入格式

The first line contains two space-separated integers $ n (1<=n<=500) $ , . Integer $ n $ represents the number of nodes of the graph $ G $ , $ m $ represents the number of edges. The second line contains $ n $ space-separated integers $ x_{i} (1<=x_{i}<=10^{6}) $ , where $ x_{i} $ represents the value of the $ i $ -th node. Consider the graph nodes are numbered from $ 1 $ to $ n $ . Each of the next $ m $ lines contains three space-separated integers $ a_{i},b_{i},c_{i} (1<=a_{i}&lt;b_{i}<=n; 1<=c_{i}<=10^{3}) $ , denoting an edge between node $ a_{i} $ and $ b_{i} $ with value $ c_{i} $ . The graph won't contain multiple edges.

输出格式

Output a real number denoting the answer, with an absolute or relative error of at most $ 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

说明

In the first sample, you can only choose an empty subgraph, or the subgraph containing only node $ 1 $ . In the second sample, choosing the whole graph is optimal.

题意翻译

题目大意：给定一个无向图，定义一个图的联通导出子图的密度为其点权之和除以边权之和。（注：边权之和为零的图密度为零）求该图的联通导出子图的最大密度。一个图的导出子图是指，选取一个顶点集，以两端点均在该顶点集中的边的全体为边集的子图。 输入格式：第一行两个整数n (1<=n<=500) ,m(0<=m<=n(n-1)/2)，分别表示图的节点数和边数。第二行n个整数xi（1<=xi<=1000000）表示第i个点的权值。后m行每行三个整数ai,bi,ci，(1<=ai,bi<=n;1<=ci<=1000)表示从ai到bi有一条权值为ci的无向边。数据保证无重边。 输出：一个浮点数，表示该图的联通导出子图密度的最大值，保留小数点后15位。如果你的答案和标准答案相差不超过10e-9，则被认为是正确的。