Luogu P5540 [BalkanOI2011] timeismoney | Minimum product spanning tree Answer key

Topic link ：P5540 [BalkanOI2011] timeismoney | Minimum product spanning tree

The question ： Give a $n$ A little bit $m$ Undirected graph of strip and edge , The first $i$ An edge has two weights $a_i$ and $b_i$ .

Find a spanning tree of the graph $T$ , bring
$$\left(\sum _{e\in T}{a}_e\right)\times \left(\sum _{e\in T}{b}_e\right)$$

Minimum

Notice that for a spanning tree , Both sides of the equation are constants

Consider mapping the spanning tree to points on the plane $(x,y)$

among $x=\sum _{e\in T}{a}_e,y=\sum _{e\in T}{b}_e$

Then the problem turns into finding a point $(x,y)$ bring $x\times y$ Minimum

It can be found that the distribution of these points has boundaries

namely $x$ Particularly large $y$ Especially when I was young and $y$ Particularly large $x$ When I was very young

These two cases correspond to points $A$ and $B$

Then there are $A$ For distance $x$ The closest point of the axis , $B$ For distance $y$ The closest point of the axis

For straight lines $AB$ , Clearly in $AB$ The above is not an optimal solution

According to the properties of inverse proportional function , It can be found that this solution must be in $A,B$ On the lower convex hull of the end point

Because we can't enumerate all spanning trees and find two-dimensional convex hull

Consider solving recursively , I don't know if you know about circumcision , It doesn't matter if I don't know

This solution is a bit like circle cutting

First find the distance line $AB$ The farthest point $C$ （ stay $AB$ below ）

Then a recursive $AC$ and $CB$ , You can find the solution

How to find $C$ How about it? ？ It can be found that at this time $S_{△ABC}$ The maximum value is taken

and $S_{△ABC}=-\frac{1}{2}\stackrel{*}{\mathrm{AB}}\times \stackrel{*}{\mathrm{AC}}$

（ notes ： What is written here is not very standard , It should actually be divided by a unit vector $\mathbf{z}$ Of , It doesn't matter ）

Push persimmon link qwq
$$\begin{array}{rl}\stackrel{*}{\mathrm{AB}}\times \stackrel{*}{\mathrm{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_B{x}_A-x_B{y}_A\end{array}$$
It can be found that the latter two items are fixed values

Therefore, we set the edge right to $(x_B-x_A)b_i+(y_A-y_B)a_i$ , Then run the minimum spanning tree

because $n$ Very small , And the analysis of the expected number of points on the convex hull is very complex

The complexity of this problem can be approximately regarded as $O(km\log m)$, among $k$ Is a small constant , Is said to be $\sqrt{\ln n}$ , Don't know much about it

The code is as follows

#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;
}

Reprint please explain the source