最小乘积生成树
问题描述
给定一张无向图，每条边都有两个正边权 $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)$
对于一些特殊问题可以进一步证明点数是线性的
