首先要知道 0/1 分数规划这个经典模型
给定 \(a_1,a_2....a_n\) 以及 \(b_1,b_2....b_n\) 求一组解 \(x_i(1\leq i \leq n，x_i \in [0,1] )\)，使下列式子最大化:
\[\frac {\sum_{i=1}^n a_i \times x_i}{\sum_{i=1}^{n} b_i \times x_i}
\]
通用解法是二分答案，我们假设二分值为 \(mid\)，且 \(mid \leq \frac {\sum_{i=1}^n a_i \times x_i}{\sum_{i=1}^{n} b_i \times x_i}\)，推一下式子就能得到：
\[\sum_{i=1}^{n} x_i (a_i-mid \times b_i) \geq 0
\]
如果左式的最大值大于等于 \(0\)，也就是存在一组解满足条件，则当前的二分值可以更大，反之更小，这个解的存在性是具有单调性的，所以二分答案的做法是成立的。
解决这类问题的关键还要看是否有合适的方式去求解左式的最大值（或最小值）。
P4951 [USACO01OPEN] Earthquake
设所选边集为 \(s\)，要求最大化 \(\Large \frac {f-\sum_{i \in s} c_i}{\sum_{i \in s} t_i}\) ，考虑二分答案，若$mid \leq $ \(\Large \frac {f-\sum_{i \in s} c_i}{\sum_{i \in s} t_i}\)，移项得 \(f- \sum_{i \in s} (mid \times t_i+c_i) \geq 0\)，对于 \(-\sum_{i \in s} (mid \times t_i+c_i)\) 这部分可以把边权赋成 \(-mid \times t_i - c_i\) 再跑一遍最大生成树求解即可。
时间复杂度 \(O(m \log m \log V)\)