Bzoj2395 [Balkan 2011]Timeismoney

Description

https://www.luogu.com.cn/problem/P5540

一条边有两个权值，求最小乘积生成树。

Solution

如果把一个生成树的 $\sum a,\sum b$ 看成一个坐标的话，最小乘积生成树的答案实际上在所有点的下凸包上。

有一个叫做 QuickHull 的凸包算法，具体过程上：

1. 先找到凸包的两个端点 $A,B$
2. 找到距离凸包最远的一个点 $C$
3. 对 $A,C$ 和 $B,C$ 作为端点继续分治下去，直到最远的点在端点里面。

感觉有点像 B 开头的最小生成树算法，如果放在普通图上做是愚蠢的，但是如果图很多点且这些点有特殊性质，就可以发挥很大作用了。

回到这道题。凸包的两个端点是好找的，分别为 $\sum a$ 最小的数和 $\sum b$ 最小的数，令这两个端点分别为 $A,B$。

现在要找距离 $A,B$ 最远的点。也就是 $S_{\triangle ABC}$ 的面积最大。用向量表示为：$S_{\triangle ABC}=-\dfrac{1}{2}\vec{AB}\times \vec{AC}$。

然后一段化简，为 $=(y_A-y_B)x_C+(x_B-x_A)y_C-x_By_A+x_Ay_B$

后面的两项都是常数，不用管。前面的两项重新赋边权以后跑最小生成树即可。

复杂度的话，点都是整点且值域是 $O(na)$，则凸包上的点是 $O((na)^{2/3})$ 级别的，而最坏要做凸包上的点的次数的最小生成树。所以复杂度为 $O(m\log m(na)^{2/3})$。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 205
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
struct yyy {
	int x,y,a,b,w;
}e[10005];
int fa[maxn],ans=1e18,ansa=1e9,ansb=1e9,n,m;
int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
bool cmp(yyy x,yyy y) {return x.w<y.w;}
pair<int,int> calc(int s,int t) {
	int i,x,y;
	for (i=1;i<=m;i++) e[i].w=s*e[i].a+t*e[i].b;
	sort(e+1,e+1+m,cmp);
	for (i=1;i<=n;i++) fa[i]=i;
	int tmp1=0,tmp2=0;
	for (i=1;i<=m;i++) {
		x=e[i].x,y=e[i].y;
		if (getfa(x)^getfa(y)) {
			fa[getfa(x)]=getfa(y);
			tmp1+=e[i].a,tmp2+=e[i].b;
		}
	}
	if (ans>tmp1*tmp2||(ans==tmp1*tmp2&&ansa>tmp1)) {
		ans=tmp1*tmp2,ansa=tmp1,ansb=tmp2;
	}
	return mk(tmp1,tmp2);
}
int cross(pair<int,int> s,pair<int,int> t) {return s.fi*t.se-s.se*t.fi;}
void solve(pair<int,int> s,pair<int,int> t) {
	auto tmp=calc(s.se-t.se,t.fi-s.fi);
	pair<int,int> tmp1,tmp2;
	tmp1=mk(s.fi-tmp.fi,s.se-tmp.se);
	tmp2=mk(t.fi-s.fi,t.se-s.se);
	if (cross(tmp1,tmp2)<0) solve(s,tmp),solve(tmp,t);
}
signed main(void){
	int i;
	read(n);read(m);
	for (i=1;i<=m;i++) {
		read(e[i].x),read(e[i].y),read(e[i].a),read(e[i].b);
		e[i].x++,e[i].y++;
	}
	auto tmp1=calc(1,0);
	auto tmp2=calc(0,1);
	solve(tmp1,tmp2);
	printf("%lld %lld\n",ansa,ansb);
	return 0;
}