模板

一个无向图，每条边有边权\(a_i\)和\(b_i\)，求一个生成树最小化

\[\sum a_i\cdot\sum b_i \]

思路：考虑将每种生成树对应成一个点\((\sum a_i,\sum b_i)\)，那么答案一定在下凸壳上（显然），但是不能直接用求凸壳的方法，因为点数过多，考虑另一种递归求凸壳的方法：

• 先找到凸壳的两个端点A，B（即\(\sum a_i\)最小和\(\sum b_i\)最小的两个点）

• 找到距离A，B有向距离最远的点C（\(\vec{AB}\)右边为正）

• 若C在\(\vec{AB}\)则分别以A和C，C和B为两个端点递归下去

显然问题在于找C，因为\(S_\triangle=\frac12 ah\)，所以找h最大即找\(S_\triangle\)最大，即最大化

\[\vec{AC}\times\vec{AB} \]

\[(c_x-a_x,c_y-a_y)\times(b_x-a_x,b_y-a_y) \]

\[(c_x-a_x)(b_y-a_y)-(b_x-a_x)(c_y-a_y) \]

由于\(A\)和\(B\)是已知的，所以相当于最大化

\[(b_y-a_y)c_x-(b_x-a_x)c_y \]

令这个为边权跑最大生成树即可（注意要求方案）

扩展

最小乘积完美匹配（同理，把最小生成树改成KM或者费用流）