最小乘积生成树

题面

给出一个 n 个点 m 条边的无向图，第 i 条边有两个权值\(a_i\)和\(b_i\)。
求该图的一棵生成树 T ，使得\((\sum_{e\in T} a_e)\times(\sum_{e\in T} b_e)\)最小

题解

首先我们将每个生成树转为二维平面上的一个点\((\sum_{e\in T} a_e),(\sum_{e\in T b_e})\)，然后发现最优解一定在凸包上
我们发现凸包上的点数不会太多
首先值域总共为\([1,nm]\)至多有\(nm\)个点
其次根据某结论：对于一个随机点集S，其凸包上的点数期望为\(O(log 2^m)\)，于是期望点数为\(log 2^m=m\)
凸包上的点并不好找，但是我们发现如果确定了斜率后求相切的点(将(a,b)变为b-ka后求最值或求(a,b)与当前端点形成的三角形面积最大)，那么直接一个mst就没了
于是我们先将斜率向量设为(1,0)和(0,1)求出最左和最右的两个点，然后每次用两个点的连线去切中间的点递归下去做即可
其实这就是quickhull算法

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 205
#define M 10005
int n, m, a[M], b[M], w1[M], w2[M], id[M], t[2], cur[2], fa[M], comp;
int ans[2];
inline int calc(int a) { return w1[a]*t[0]+w2[a]*t[1]; }
inline int calc(int x, int y) { return x*t[0]+y*t[1]; }
bool cmp(int a, int b) { return calc(a)<calc(b); }
int findfa(int x) { return x==fa[x]?x:fa[x]=findfa(fa[x]); }
inline void merge(int x, int y, int w1, int w2)
{
	x=findfa(x), y=findfa(y);
	if(x==y) return;
	++comp, cur[0]+=w1, cur[1]+=w2;
	fa[x]=y;
}
inline void upt(void) { 1ll*cur[0]*cur[1]<1ll*ans[0]*ans[1]?ans[0]=cur[0], ans[1]=cur[1]:0; }
inline int gmx(void)
{
	std::sort(id+1, id+m+1, cmp);
	cur[0]=cur[1]=comp=0;          
	for(int i=1; i<=n; ++i) fa[i]=i;
	for(int i=1; comp<n-1; ++i) merge(a[id[i]], b[id[i]], w1[id[i]], w2[id[i]]);
	upt();
}
void solve(int x1, int y1, int x2, int y2)
{
	t[0]=y1-y2, t[1]=x2-x1;
	gmx();
	int x3=cur[0], y3=cur[1];
	if((calc(x3, y3)==calc(x1, y1))||(calc(x3, y3)==calc(x2, y2))) return;
	solve(x1, y1, x3, y3), solve(x3, y3, x2, y2);
}
int main()
{
	freopen("in.in", "r", stdin);
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; ++i) scanf("%d%d%d%d", a+i, b+i, w1+i, w2+i), ++a[i], ++b[i], id[i]=i;
	ans[0]=ans[1]=0x3f3f3f3f;
	int x1, y1, x2, y2;
	t[0]=1, t[1]=0;
	gmx();
	x1=cur[0], y1=cur[1];
	t[0]=0, t[1]=1;
	gmx();
	x2=cur[0], y2=cur[1];
	solve(x1, y1, x2, y2);
	printf("%d %d\n", ans[0], ans[1]);
	return 0;
}

总结

此题思想为凸优化，去掉无用点
还通过神似带权二分的优化方式将不好直接求解的问题转换