Description：

每条边有两个权值 $x$ 和 $y$ ，求一个生成树使得 $\sum x\times \sum y$ 最小。

$1\leqslant n\leqslant 200,1\leqslant m\leqslant 10000$

Solution：

我们可以把每个生成树看成二维平面上的点 $(\sum x,\sum y)$ ，那么问题就转化成了找一个点 $x\times y$ 最小，这个点应该在下凸壳上，那么我们先找两个一定在下凸壳上的点 $A(minx,y)$ 和 $B(x,miny)$ ，然后在直线下方找一个在凸包上且 $x\times y$ 最小的点，我们令那个点为 $C$ ，那么我们让 $\overrightarrow{AB}\times \overrightarrow{AC}$ 最小也就是 $S_{\triangle ABC}$ 最大，那么： $$ \begin{align} 2S&=\overrightarrow{AB}\times \overrightarrow{AC}\\ &=(B.x-A.x,B.y-A.y)\times (C.x-A.x,C.y-A.y)\\ &=(B.x-A.x)\times (C.y-A.y)-(B.y-A.y)\times (C.x-A.x)\\ \end{align} $$ 这样求到最后只与 $C$ 有关的项是： $$ (B.x-A.x)\times C.y-(B.y-A.y)\times C.x\\ $$ 那么我们只要把每条边的权值看成 $(B.x-A.x)\times y[i]-(B.y-A.y)\times x[i]$ 再做最小生成树即可，然后这样无限递归下去直到直线的一侧不存在点。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 210

#define MAXM 10010

typedef long long ll;

struct edges

{

	int u,v,x,y;

	ll w;

}es[MAXM];

bool cmp_w(edges a,edges b){return a.w < b.w;}

struct point

{

	ll x,y;

	point(ll x_ = 0,ll y_ = 0){x = x_;y = y_;}

};

point operator - (point a,point b){return (point){a.x - b.x,a.y - b.y};}

ll operator * (point a,point b){return a.x * b.y - a.y * b.x;}

int f[MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

point kruskal()

{

	sort(es + 1,es + 1 + m,cmp_w);

	memset(f,0,sizeof(f));

	point res;

	for(int i = 1;i <= m;++i)

	{

		int p = find(es[i].u),q = find(es[i].v);

		if(p == q)continue;

		res.x += es[i].x;res.y += es[i].y;

		f[p] = q;

	}

	return res;

}

#define INF 0x3f3f3f3f3f3f3f3f

point ans;

point min(point a,point b)

{

	if(a.x * a.y < b.x * b.y)return a;

	else return b;

}

void solve(point A,point B)

{

	ans = min(ans,min(A,B));

	for(int i = 1;i <= m;++i)es[i].w = (B.x - A.x) * es[i].y - (B.y - A.y) * es[i].x;

	point C = kruskal();

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

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

	return;

}

int main()

{

	ans.x = INF;ans.y = INF;

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

	for(int i = 1;i <= m;++i)

	{

		es[i].u = rd() + 1;es[i].v = rd() + 1;

		es[i].x = rd();es[i].y = rd();

	}

	for(int i = 1;i <= m;++i)es[i].w = es[i].x;

	point A = kruskal();

	for(int i = 1;i <= m;++i)es[i].w = es[i].y;

	point B = kruskal();

	solve(A,B);

	cout << ans.x << " " << ans.y << endl;

	return 0;

}