关于 DZY Loves Physics 的近10条评论(全部评论)
弱弱地问一句题目和题干有什么关联吗。小朋友。 2019-07-02 20:59 3楼
火钳刘明 wire 2019-07-02 17:18 2楼
留名 ^ ^ Theresis 2019-07-02 17:07 1楼

3201. [CF 444A] DZY Loves Physics

★★ 输入文件：dzy.in 输出文件：dzy.out 简单对比
时间限制：1 s 内存限制：256 MiB

给定一个$n$个点$m$条边的无向图，其中每一个点和边都有权值，求一个点数大于等于2的导出连通子图，使得该子图中点权和除以边权和最大。求这个最大的边权和。

第一行有两个整数$n$($1\leq n \leq 500$)和$M$($0\leq m \leq \frac{n(n-1)}{2}$)。

第二行有N个整数是各点的权值$x_i$($1\leq x_i\leq 10^6$)。

接下来有M行，每行有三个整数$x,y,w$($1\leq x < y \leq n, 1\leq w \leq 10^3 $)，分别表示图中边的两个端点和边权。

输出点权和除以边权和最大值，保留到小数点后两位。

1 0
1

0.00

2 1
1 2
1 2 1

3.00

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

2.97