题目描述

给出一个无向图联通图，每条边有 2 个权值 $a_i, b_i$求出生成树，是的下面的式子最小

这样的生成树我们称为最小比率生成树，请输出这个值，答案保留 2 位有效数字

输入格式

第一行包含两个整数 $n, m$，表示该图共有 $n$ 个结点和 $m$ 条无向边。

接下来 $m$ 行每行包含 4 个整数 $x_i,y_i,a_i, b_i$，表示有一条权值为 $a_i, b_i$ 的无向边连接结点 $x_i,y_i$。

输出格式

输出最小比率生成树的值，答案保留 2 位有效数字

4 5
1 2 4 3
1 3 3 7
1 4 5 3
2 3 2 3
3 4 3 2

0.67

提示

【样例 #1 解释】

• 选取 (1 3 3 7), (2 3 2 3), (3 4 3 2)
• 那么 $(3+2+3)/(7+3+2)=0.67$
• 思考：当题目要求的是一个比值时，一般要怎么做？
• 请参考 LS1078【入门】最大化平均值 的解法

数据规模与限制

• $1 \leq n \leq 10^3$
• $1 \leq m \leq 10^4$
• $1 \leq a_i, b_i \leq 10^4$

来源

• poj_2728