Luogu5540 最小乘积生成树

Luogu5540 最小乘积生成树

题目链接：洛谷

题目描述：对于一个\(n\)个点\(m\)条边的无向连通图，每条边有两个边权\(a_i,b_i\)，求使\((\sum a_i)\times (\sum b_i)\)最小的生成树。

数据范围：\(n\le 200,m\le 10000,a_i,b_i\le 255\)

这题是一道非常妙的计算几何题目。

我们对于每个生成树，用\((\sum a_i,\sum b_i)\)这个二维平面上的点来表示它，那么就是求所有点中横坐标乘纵坐标的最小值。

画画图就可以发现，答案只有可能在下凸包上，为什么呢？

因为如果\(C\)在线段\(AB\)上方，其中\(x_Ay_A=x_By_B\)，因为反比例函数下凸，所以\(x_Cy_C>x_Ay_A\)。

但是生成树可能有很多个，怎么得到下凸包上的点呢？

Step1 求最靠近\(x,y\)轴的两个点\(A,B\)

为什么呢？因为\(A,B\)两个点必定在下凸包上面。令\(w_i=a_i\)或\(b_i\)用最小生成树求\(A,B\)。

Step2 求\(C\)在直线\(AB\)下方且\(S_{\Delta ABC}\)最大

为什么呢？因为\(C\)点必定在下凸包上面，否则它不是最大的点。我们发现

\[\begin{aligned}
-\frac{1}{2}S_{\Delta ABC}&=\overrightarrow{AB}\times \overrightarrow{AC} \\
&=(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A) \\
&=((x_A-x_B)y_A-(y_A-y_B)x_A)+(x_B-x_A)y_C-(y_B-y_A)x_C
\end{aligned}
\]

令\(w_i=(x_B-x_A)b_i-(y_B-y_A)a_i\)就会得到\(C\)

Step3 将(A,C)和(C,B)代入Step2递归

这样就可以求出下凸包上所有的点。那什么时候终止递归呢？当然就是\(C\)不存在，或者说求出的\(C\)在\(AB\)上方。

时间复杂度为\(O(km\log m)\)，其中\(k\)为下凸包上点的个数，在随机数据下不会很大。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef long long LL;

const int N = 10003;

int n, m, a[N], b[N], fa[N];

struct Point {

	int x, y;

	inline Point(int _x = 0, int _y = 0): x(_x), y(_y){}

	inline Point operator - (const Point &o) const {return (Point){x - o.x, y - o.y};}

} A, B, ans(1e9, 1e9);

inline LL cross(Point a, Point b){return (LL) a.x * b.y - (LL) b.x * a.y;}

struct Edge {

	int u, v, w, id;

	inline bool operator < (const Edge &o) const {return w < o.w;}

} e[N];

inline int getfa(int x){return x == fa[x] ? x : fa[x] = getfa(fa[x]);}

inline Point Kruskal(){

	Point res; sort(e + 1, e + m + 1);

	for(Rint i = 1;i <= n;i ++) fa[i] = i;

	for(Rint i = 1, p = 1;i <= m && p < n;i ++){

		int u = getfa(e[i].u), v = getfa(e[i].v);

		if(u != v){fa[u] = v; ++ p; res.x += a[e[i].id]; res.y += b[e[i].id];}

	}

	LL Ans = (LL) ans.x * ans.y, Res = (LL) res.x * res.y;

	if(Ans > Res || Ans == Res && ans.x > res.x) ans = res;

	return res;

}

inline void solve(Point A, Point B){

	for(Rint i = 1;i <= m;i ++) e[i].w = (A.y - B.y) * a[e[i].id] - (A.x - B.x) * b[e[i].id]; Point C = Kruskal();

	if(cross(B - A, C - A) >= 0) return;

	solve(A, C); solve(C, B);

}

int main(){

	scanf("%d%d", &n, &m);

	for(Rint i = 1;i <= m;i ++) scanf("%d%d%d%d", &e[i].u, &e[i].v, a + i, b + i), ++ e[i].u, ++ e[i].v, e[i].id = i;

	for(Rint i = 1;i <= m;i ++) e[i].w = a[e[i].id]; Point A = Kruskal();

	for(Rint i = 1;i <= m;i ++) e[i].w = b[e[i].id]; Point B = Kruskal();

	solve(A, B); printf("%d %d", ans.x, ans.y);

}