AT_arc026_4.[ARC026D] 道を直すお仕事

在“ダイナミック王国”中有 $N$ 个村庄，编号从 $0$ 到 $N-1$。这些村庄原本通过 $M$ 条道路连成一个整体。“连成一个整体”指的是，从任意一个村庄出发，都可以通过若干条道路到达任意其他村庄。某天，一场大灾害摧毁了所有的道路，导致村庄之间无法互相通行。你受国王高桥君的委托，负责修复道路，使“ダイナミック王国”的 $N$ 个村庄重新连成一个整体。

你首先估算了修复每条道路所需的费用和时间。接下来，你需要计算在合理选择要修复的道路时，“能够收支平衡的最低时薪”的最小值。“能够收支平衡的最低时薪”指的是，当“修复道路所需的总时间”乘以“时薪”恰好等于“修复道路所需的总费用”时的“时薪”金额。

请注意，不一定需要修复所有的道路，也可以修复一些对连通村庄整体并非必要的道路。

输入通过标准输入按以下格式给出。

$N$ $M$
$A_1$ $B_1$ $C_1$ $T_1$
$A_2$ $B_2$ $C_2$ $T_2$
$\vdots$
$A_M$ $B_M$ $C_M$ $T_M$

• 第 $1$ 行包含两个整数 $N\ (2 \leq N \leq 10^4)$ 和 $M\ (1 \leq M \leq 10^4)$，分别表示村庄的数量和道路的数量。
• 接下来的 $M$ 行，每行包含四个整数 $A_i\ (0 \leq A_i \leq N-1)$，$B_i\ (0 \leq B_i \leq N-1)$，$C_i\ (1 \leq C_i \leq 10^6)$，$T_i\ (1 \leq T_i \leq 10^6)$，表示有一条连接村庄 $A_i$ 和 $B_i$ 的道路，修复这条道路需要费用 $C_i$，需要时间 $T_i$。

此外，关于道路的信息，保证以下条件成立：

• 对所有 $i$，有 $A_i \neq B_i$。
• 对所有 $i \neq j$，有“$A_i \neq A_j$ 或 $B_i \neq B_j$”且“$A_i \neq B_j$ 或 $B_i \neq A_j$”。

请输出“能够收支平衡的最低时薪”的最小值，输出一行。

只要输出的绝对误差不超过 $10^{-2}$ 即可。

输出末尾需换行。

部分分

本题设置了部分分。

• 若能正确解决所有 $M \leq 16$ 的测试用例，可获得 $20$ 分。

样例解释 1

在本例中，为了使所有村庄连通，必须修复所有道路。修复所有道路所需的总费用为 $10$，总时间为 $5$，因此能够收支平衡的最低时薪为 $2$。由于允许误差 $10^{-2}$，输出 $2.01$ 或 $1.99$ 等也可以。

样例解释 2

在本例中，修复第 $1$ 条和第 $3$ 条道路时，“能够收支平衡的最低时薪”为 $1.5$，且为最小值。

样例解释 3

在本例中，修复所有道路时，“能够收支平衡的最低时薪”为 $1.333\ldots$，且为最小值。

由 ChatGPT 4.1 翻译