最优比率生成树

给定图$G=(V,E,c,p)$，其中$c: E(G)\to \R,p: E(G)\to \R_+$，求一个$G$的生成树$T$，使得

$$\frac{\sum_{e\in E(T)}c(e)}{\sum_{e\in E(T)}p(e)}$$

最小。

考虑Kruskal的Megiddo方法，设最优解是$\lambda^*$。我们定义新费用$c’=c-\lambda^*p$。

在Kruskal最开始的排序时，每次遇到$c’_i\overset{?}{<}c_j’$时，其实是：

\[
\frac{c(e_i)-c(e_j)}{p(e_i)-p(e_j)}\overset{?}{<}\lambda^*
\]

把左边这个分式设为$\lambda$定义新费用，调用Kruskal看这个费用下的最小生成树大小M。

如果$M< 0$，说明$\lambda$太大了，最优比值$\lambda^*$应该更小（因为最优比率取到的生成树大小是0，调小调大参数会让所有生成树的大小都同时按不同比率增大或缩小，如果$\lambda$比最优比率大，算出的最小生成树的M也一定比0小）

$M> 0$类似。

于是每次调用Kruskal作为预言机得到新费用在最优比值下的排序结果，即使我们尚不知道$\lambda^*$的实际值，然后按这个结果再调用一次Kruskal即可。

总复杂度$O(m\log m\cdot m\alpha(n))\approx O(m^2\log n)$