最小乘积生成树

问题描述

bzoj 2395

给定一张无向图,每条边都有两个正边权 $a$ 和 $b$

一棵生成树的权值定义为所有边 $a$ 的权值和乘上 $b$ 的权值和

求权值最小的生成树

$1 \le n \le 200, 1 \le m \le 100000, 0 \le u, v < n, 0 \le a,b \le 255$

题解

设 $x=\sum a,y=\sum b$,用 $(x,y)$ 来表示一棵生成树

把所有的 $(x,y)$ 标到二维平面上,则答案一定在下凸壳上面


考虑线段 $(a, b) - (a + c, b + d)(c > 0, d < 0)$

最小化 $(a + ct)(b + dt) = ab + (ad + bc)t + cdt^2(0 ≤ t ≤ 1)$

$ad + bc + cd \ge 0$ 时,$t = 0$

$ad + bc + cd < 0$ 时,$t = 1$

求出所有凸壳上的点即可


找到 $x$ 最小的点 $A$ 和 $y$ 最小的点 $B$

找到 $AB$ 靠原点一侧最远的点 $C$

最大化 $\vec{AB} \times \vec{AC}$

$$
\begin{aligned}
&(B.x − A.x)(C.y − A.y) − (B.y − A.y)(C.x − A.x) \\
=&(B.x-A.x)C.y-(B.y-A.y)C.x+((C.x-A.x)-(B.x-A.x))A.y
\end{aligned}
$$

给出 $w_a, w_b$,找出 $w_a\sum a+w_b\sum b$ 最小的生成树

递归 $AC$ 与 $CB$,直到左下方没有点为止


总点数不超过 ${m \choose n-1}$

如果把点视为随机的话,凸包上的点数为 $O(n \log m)$

时间复杂度 $O(n^3 \log n)$


假设已经知道了答案 $t$,那么所有点都在 $y =\frac{t}{x}$ 上方

其中答案点 $A$ 正好落在函数上

作函数的切线 $y = w_ax + w_b$,那么答案点 $A$ 一定是 $−w_ax + y$ 最小的点


一定存在常数 $k$ 使得答案同时也是 $\sum a+k\sum b$ 最小的点

如果已经知道了 $k$ 的大小,排序贪心

只需要知道这个 $k$ 值时边的相对顺序

任意两条边 $i$ 和 $j$ 在 $k = f_{i,j}$ 时权值相同

$m^2$ 个 $f_{i,j}$ 将数轴划分成了 $m^2$ 段,仅有 $m^2$ 个相对顺序

做 $m^2$ 次最小生成树,$O(m^3)$,使用 $LCT$ 优化,$O(m^2 \log n)$


对于凸包上的点,一定存在区间 $[l, r] (l < r)$ 使得对于每一个 $k \in [l, r]$,这个点都是 $\sum a+k\sum b$ 最小的点

凸包上的点数不超过 $O(m^2)$

对于一些特殊问题可以进一步证明点数是线性的