P5540 【模板】最小乘积生成树

题目链接https://www.luogu.org/problem/P5540

---

题意

给出一个 $n$ 个点 $m$ 条边的无向图，第 $i$ 条边有两个权值 $a_i$和$b_i$ 求该图的一棵生成树 $T$ ，使得($\sum a_e)\ast (\sum b_e)$最小。

---

题解

https://www.luogu.org/problemnew/solution/P5540

把$\sum a_e$看作$x$，$\sum b_e$看作$y$，答案就变成了平面上的一个坐标点$(x,y)$。这样平面上最多一共有$n^{n-2}$个点（生成树的个数），现在要求出一个点使得$x\times y$最小。很容易想到答案在凸包的左下角上，现在就是想办法求出该点。

如果点$A$是$x$最小的点，$B$是$y$最小的点，那么点$A$和点$B$一定是在凸包上。假设点$C$是在$AB$的左下处，那点$C$一定更优，所以我们要找到点一个在$AB$左下处的点$C$使得三角形$ABC$面积最大，或者$AB\times AC$最小。这样求出来的点$C$也是在凸包上的。

推一下式子：$AB\times AC=(x_B-x_A)y_C+(y_A-y_B)x_C-(x_B-x_A)y_A+(y_B-y_A)x_A$

后面两项是常数，所以我们只要让$(x_B-x_A)y_C+(y_A-y_B)x_C$最小即可。对此我们只要对每条边设一个权值为：$(x_B-x_A)a[i]+(y_A-y_B)b[i]$，跑一边最小生成树就可以求出点$C$。

求出来点$C$后，只需要递归求在$AC$和$CB$左下方的点即可。

因为一张$n$个点的图，凸包上的点数期望是$\sqrt{\ln n}$，我们最多有$n^{n-2}$个点，所以最后的复杂度是$O(mlog(m)\sqrt{\ln n^{n-2}})$

---

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+7; struct Edge{ int u,v,a,b,w; bool operator<(const Edge k)const{return w<k.w;} }e[N]; int n,m; struct Point{ int x,y; Point operator - (const Point k)const{return (Point){x-k.x,y-k.y};} }ans; int cross(Point k1,Point k2){return k1.x*k2.y-k2.x*k1.y;} int fa[N]; int fd(int x){return x==fa[x]?x:fa[x]=fd(fa[x]);} Point kruskal(){ Point res=(Point){0,0}; sort(e+1,e+1+m); for(int i=0;i<n;i++) fa[i]=i; for(int i=1;i<=m;i++){ int u=e[i].u,v=e[i].v; int fu=fd(u),fv=fd(v); if(fu==fv) continue; fa[fu]=fv; res.x+=e[i].a; res.y+=e[i].b; } ll now=1ll*ans.x*ans.y; ll tmp=1ll*res.x*res.y; if(now>tmp||(now==tmp&&ans.x>res.x)) ans=res; return res; } void solve(Point A,Point B){ for(int i=1;i<=m;i++) e[i].w=(A.y-B.y)*e[i].a+(B.x-A.x)*e[i].b; Point C=kruskal(); if(cross(B-A,C-A)>=0) return; solve(A,C);solve(C,B); } int main() { ans.x=ans.y=256*200; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].a,&e[i].b); } for(int i=1;i<=m;i++) e[i].w=e[i].a; Point A=kruskal(); for(int i=1;i<=m;i++) e[i].w=e[i].b; Point B=kruskal(); solve(A,B); printf("%d %d\n",ans.x,ans.y); }