洛谷P5540 [BalkanOI2011] timeismoney | 最小乘积生成树 题解

题目链接：P5540 [BalkanOI2011] timeismoney | 最小乘积生成树

题意：给出一个 $n$ 个点 $m$ 条边的无向图，第 $i$ 条边有两个权值 $a_i$ 和 $b_i$ 。

求该图的一棵生成树 $T$ ，使得

$$\left(\sum_{e\in T}a_e\right)\times\left(\sum_{e\in T}b_e\right)$$

最小

注意到对于一棵生成树，式子中的左右两边均为常数

考虑将生成树映射到平面上的点 $(x,y)$

其中 $x=\sum\limits_{e\in T}a_e,y=\sum\limits_{e\in T}b_e$

那么问题就转化为了求一个点 $(x,y)$ 使得 $x\times y$ 最小

可以发现这些点的分布存在边界

即 $x$ 特别大 $y$ 特别小的时候以及 $y$ 特别大 $x$ 特别小的时候

这两种情况分别对应点 $A$ 和 $B$

则有 $A$ 为距离 $x$ 轴最近的点， $B$ 为距离 $y$ 轴最近的点

对于直线 $AB$ ，显然在 $AB$ 上方的不是优解

根据反比例函数的性质，可以发现这个解一定在以 $A,B$ 为端点的下凸包上

由于我们不可能枚举出所有的生成树然后求二维凸包

考虑递归求解，不知道大家知不知道割圆术，不知道也没关系

这个解法有点像割圆术

首先找出距离直线 $AB$ 最远的点 $C$ （在 $AB$ 下方）

然后递归 $AC$ 和 $CB$ ，即可求出解

如何寻找 $C$ 点呢？可以发现此时 $S_{\triangle ABC}$ 取到了最大值

而 $S_{\triangle ABC} = -\dfrac{1}{2}\overset{\longrightarrow}{AB}\times \overset{\longrightarrow}{AC}$

（注：这里写的不是很规范，其实应该除以一个单位向量 $\boldsymbol{z}$ 的，不重要不管了）

推柿子环节 qwq

$$\begin{aligned} \overset{\longrightarrow}{AB}\times \overset{\longrightarrow}{AC} &= (x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\\ &=(x_B-x_A)\times y_C + (y_A-y_B)\times x_C + y_Bx_A-x_By_A \end{aligned}$$

可以发现后面两项是定值

因此我们将边权设为 $(x_B-x_A)b_i+(y_A-y_B)a_i$ ，然后跑最小生成树即可

由于 $n$ 很小，且凸包上的期望点数分析极其复杂

本题复杂度可以近似看作 $O(km\log m)$，其中 $k$ 为一个小常数，据说是 $\sqrt{\ln n}$ ，不太清楚

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e2+15)
#define M (int)(1e4+15)
int n,m;
struct Edge
{
    int u,v,a,b,w,next;
}e[M];
struct vct
{
    int x,y;
}ans;
int f[N];
vct operator-(vct a,vct b){return (vct){a.x-b.x,a.y-b.y};}
int cross(vct a,vct b){return a.x*b.y-a.y*b.x;}
void init(){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){u=find(u);v=find(v);f[u]=v;}
vct kruskal()
{
    sort(e+1,e+1+m,[](Edge a,Edge b){
        return a.w<b.w;
    });
    init();
    vct res={0,0};
    int cnt=0;
    for(int i=1; i<=m; i++)
    {
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v)
        {
            merge(u,v);
            res.x+=e[i].a;
            res.y+=e[i].b;
            if(++cnt==n-1)break;
        }
    }
    int Ans=ans.x*ans.y,Res=res.x*res.y;
    if(Ans>Res||Ans==Res&&ans.x>res.x)ans=res;
    return res;
}
void solve(vct A,vct B)
{
    for(int i=1; i<=m; i++)
        e[i].w=e[i].b*(B.x-A.x)+e[i].a*(A.y-B.y);
    vct C=kruskal();
    if(cross(B-A,C-A)>=0)return;
    solve(A,C);solve(C,B);

}
signed main()
{
    read(n);read(m);
    ans={0x3f3f3f3f,0x3f3f3f3f};
    for(int i=1; i<=m; i++)
    {
        read(e[i].u);read(e[i].v);
        read(e[i].a);read(e[i].b);
        e[i].u++;e[i].v++;
    }
    for(int i=1; i<=m; i++)
        e[i].w=e[i].a;
    vct A=kruskal();
    for(int i=1; i<=m; i++)
        e[i].w=e[i].b;
    vct B=kruskal();
    solve(A,B);
    printf("%lld %lld\n",ans.x,ans.y);
    return 0;
}