题意
给一个无向图，边有两个权 \(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)\) 之类东西？这里只是提一提。
感谢花花老师，感谢钱哥。
标签：timeismoney,le,BalkanOI2011,text,sum,凸包,权值,左下角,P5540 From： https://www.cnblogs.com/kyeecccccc/p/17413609.html