Skip to content

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 \)的图。

Input Format

第一行为两个数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 \)

Output Format

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

Sample Input

2 1
1 2
1 2 1

Sample Output

3.000000000

Oops! 本题目还没有解答!

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

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

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