洛谷 P5540 [BalkanOI2011] timeismoney | 最小乘积生成树
阅读原文时间:2023年08月17日阅读:2

给一个无向图,边有两个权 \(a\) 和 \(b\),定义一个生成树的权值是 \(\left(\sum\limits_{e\in T}a_e\right)\left(\sum\limits_{e\in T}b_e\right)\),求最小权值生成树。权值相同请最小化 \(a\) 的和。

\(1\le n\le 200, 1\le m\le 10000, 0\le a_e, b_e\le 255\)。

纯粹记录一些结论和一个方法,启发性是有的,但是不是太大。首先观察题目,这个数据范围不知所云,上面的东西完全拆不开,好,我已经废了。考虑把一个生成树写成一个点 \((\sum a, \sum b)\),那么待求的东西在左下凸包上。采取在 UOJ 群广为人知的 quick hull 算法来求解(难绷)。具体地,首先确定两个在凸包上的点,然后连一条线段,找到离这个线段最远的点,它肯定也在凸包上,然后分成两半接着做,做到斜线左下角没有点了就返回。这样你的时间是 \(\text{凸包点数}\times\text{求左下角的时间}\)。我们发现这是个整点凸包,它的复杂度上界不过是 \((\sum a)^\frac23\)。而求左下角最远的点,考虑写出叉积式子,最大化叉积,然后就可以变成一个普通 MST 问题,其中每条边的边权是 \(a, b\) 带上系数加起来的一个值。复杂度就很对。

另一个结论是,如果点集随机那么凸包大小是 \(\log\text{点数}\) 级别的。这个可以考虑按照 \(x\) 排序后 \(y\) 的前缀最大值序列长度,凸包大小不会超过它的级别。当然这题不是随机的,哪怕是似乎也用处不大,是不是只能得到 \(\log (n^n)\) 之类东西?这里只是提一提。

感谢花花老师,感谢钱哥。