P5540 [BalkanOI2011] timeismoney | 最小乘积生成树

题意：
给你一个$n$个点$m$条边的无向图，每个边有两个权值$a_i,b_i$，让你求出一个$({\sum }_{i\in T}{a}_i)({\sum }_{i\in T}{b}_i)$最小的生成树。

思路：
首先，对于一棵生成树T，我们令$x_T={\sum }_{i\in T}{a}_i,y_T={\sum }_{i\in T}{b}_i$。那么$T$就可以对应平面上面一个点$(x_T,y_T)$。

那么我们要求的就是$x\ast y$最小的$T$，很容易发现这一定是在所有点的下凸壳上。

根据定理，下凸壳上的点数量很少，大概是$\sqrt{lnn!}$个。这网上有很多种说法。

现在考虑怎么找出这个凸壳。

首先，$x$最小的点和$y$最小的点一定在凸壳上面，这两个都可以用最小生成树来求，分别设为$A,B$。

然后，求出距离线段$AB$最远的点，这个点肯定也在凸壳上面。我们用差乘来求距离。令$A(x_1,y_1),B(x_2,y_2)$，你要求的点是$C(x,y)$。$\overrightarrow{AB}\times \overrightarrow{AC}=(x_2-x_1)(y-y_1)-(x-x_1)(y_2-y_1)$。就是要求$(y_1-y_2)x+(x_2-x_1)y$的最小值。
很显然这个东西又可以用最小生成树求解,因此这就变成了一个递归求解的过程。
时间复杂度$O(nlogn\sqrt{\ln n!})$。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){
    x=0;int f=0;char s=getchar();
    while(!isdigit(s))f|=s=='-',s=getchar();
    while(isdigit(s))x=x*10+s-48,s=getchar();
    x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
    if(x<0)putchar('-'),x=-x;
    do{buf[++cc]=int(x%10);x/=10;}while(x);
    while(cc)putchar(buf[cc--]+'0');
}
const int N=210,M=1e4+10;
int n,m;
struct point{
    ll x,y;
    point(ll xx=0,ll yy=0):x(xx),y(yy){}
    point operator-(const point &k)const{
        return point(x-k.x,y-k.y);
    }
    bool operator<(const point &k)const{
        if(x*y!=k.x*k.y)return x*y<k.x*k.y;
        return x<k.x;
    }
    void output(){qw(x),putchar(' '),qw(y),puts("");}
};
point ans=point(1e9,1e9);
ll det(point a,point b){
    return a.x*b.y-a.y*b.x;
}
ll dot(point a,point b){
    return a.x*b.x+a.y*b.y;
}
struct edge{
    int x,y;ll w;int id;
}e2[M];
struct edge2{
    int x,y;ll w1,w2;
}e[M];
int fa[N];
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
bool cmp(edge p1,edge p2){
    return p1.w<p2.w;
}
point kruskal(){
    sort(e2+1,e2+m+1,cmp);
    rep(i,1,n)fa[i]=i;
    ll s1=0,s2=0;
    rep(i,1,m){
        int x=e2[i].x;
        int y=e2[i].y;
        if(findfa(x)!=findfa(y)){
            fa[findfa(x)]=findfa(y);
            s1+=e[e2[i].id].w1;
            s2+=e[e2[i].id].w2;
        }
    }
    ans=min(ans,point(s1,s2));
    return point(s1,s2);
}
void solve(point p1,point p2){
    rep(i,1,m){
        e2[i].x=e[i].x;
        e2[i].y=e[i].y;
        e2[i].id=i;
        e2[i].w=(p1.y-p2.y)*e[i].w1+(p2.x-p1.x)*e[i].w2;
    }
    point mid=kruskal();
    if(det(p2-p1,mid-p1)>0)return;
    if(det(p2-p1,mid-p1)==0&&dot(p1-mid,p2-mid)>=0)return;
    solve(p1,mid),solve(mid,p2);
}
void solve(){
    qr(n),qr(m);
    rep(i,1,m){
        qr(e[i].x),qr(e[i].y),qr(e[i].w1),qr(e[i].w2);
        e[i].x++,e[i].y++;
    }
    rep(i,1,m){
        e2[i].x=e[i].x;
        e2[i].y=e[i].y;
        e2[i].id=i;
        e2[i].w=e[i].w1;
    }
    point p1=kruskal();
    rep(i,1,m){
        e2[i].x=e[i].x;
        e2[i].y=e[i].y;
        e2[i].id=i;
        e2[i].w=e[i].w2;
    }
    point p2=kruskal();
    solve(p1,p2);
    ans.output();
}
int main(){
    int tt;tt=1;
    while(tt--)solve();
    return 0;
}