Codeforces Round #254 (Div. 2)444A - DZY Loves Physics (枚举权值求最大)-白红宇的个人博客

Codeforces Round #254 (Div. 2)444A - DZY Loves Physics (枚举权值求最大)

发布日期：2021-11-06 16:56:37 浏览次数：6 分类：技术文章

本文共 2177 字，大约阅读时间需要 7 分钟。

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:

$\text{[math]}$

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:

$\text{[math]}$ ;

edge $\text{[math]}$ if and only if $\text{[math]}$ , and edge $\text{[math]}$ ;

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.

$\text{[math]}$

Input

The first line contains two space-separated integers n (1 ≤ n ≤ 500), $\text{[math]}$ . 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⁶), 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 < b_i ≤ n; 1 ≤ c_i ≤ 10³), denoting an edge between node a_i and b_i with value c_i. The graph won't contain multiple edges.

Output

Output a real number denoting the answer, with an absolute or relative error of at most 10^- 9.

          Sample test(s) 
            input 
1 01
            output 
0.000000000000000
            input 
2 11 21 2 1
            output 
3.000000000000000
            input 
5 613 56 73 98 171 2 561 3 291 4 422 3 952 4 883 4 63
            output 
2.965517241379311

Note

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.

AC代码：

#include 
   
    #define max(a,b) a>b?a:b;//author:XXYYint main(){	int n,m,x,y,z,i,v[505];	double ans=0;	scanf("%d%d",&n,&m);	for(i=1;i<=n;i++)		scanf("%d",&v[i]);	while(m--){		scanf("%d%d%d",&x,&y,&z);		ans=max(ans,1.0*(v[x]+v[y])/z);	}	printf("%.12lf\n",ans);	return 0;}

转载地址：https://blog.csdn.net/YJX_xx/article/details/37512301 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：edward_mj退役经验帖(浙大2届Final队员陈伟杰的退役贴)

下一篇：Codeforces Round #254 (Div. 2) 445B - DZY Loves Chemistry （并查集）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章