正題

題目鏈接:https://www.luogu.com.cn/problem/P5540

---

題目大意

給出$n$個點$m$條邊邊權是一個二元組$(a_i,b_i)$，求出一棵生成樹最小化
$$(\sum _{e\in T}{a}_e)\times (\sum _{e\in T}{b}_e)$$
的情況下最小化${\sum }_{e\in T}{a}_e$

$1\le n\le 200,1\le m\le 10^4$

---

解題思路

這種帶乘積的可以維護凸殼，對于一棵生成樹$T$我們視為一個$({\sum }_{e\in T}{a}_e,{\sum }_{e\in T}{b}_i)$的點，這樣我們打答案一定在下凸殼上。

可以用一種分治求凸殼的方法，我們先找出下凸殼的兩個端點（$x$最小的和$y$最小的）記為$A,B$，然后找到一個在$A$與$B$的連邊下面的一個最凸的點$C$（可以視為最大化$S_{△ACB}$，這樣$C$一定在凸殼上），然后分治下去做$AC$和$CB$。

考慮怎么求這個$C$，就是最大化$AC\times CB$
$$(x_C?x_A)(y_B?y_A)?(x_B?x_A)(y_C?y_A)$$
$$=x_C(y_B?y_A)?y_C(x_B?x_A)+y_A(x_B?x_A)?x_A(y_B?y_A)$$
然后就是相當于最小化$x_C(y_B?y_A)+y_C(x_A?x_B)$，拿這個當邊權跑就可以跑出$C$了。

然后時間復雜度據說是$O(m\log m\sqrt{\ln n!})$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=210,M=1e4+10; struct node{ll x,y,w,id; }e[M]; struct point{ll x,y;point(ll xx=0,ll yy=0){x=xx;y=yy;return;} }ans; ll n,m,x[M],y[M],a[M],b[M],fa[N]; point operator-(point x,point y) {return point(x.x-y.x,x.y-y.y);} ll operator*(point x,point y) {return x.x*y.y-x.y*y.x;} bool cmp(node x,node y) {return (x.w==y.w)?(a[x.id]<a[y.id]):(x.w<y.w);} ll find(ll x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} point Kruskal(){ll cnt=0;point res=0;for(ll i=1;i<=n;i++)fa[i]=i;sort(e+1,e+1+m,cmp);for(ll i=1;i<=m;i++){ll x=find(e[i].x),y=find(e[i].y);if(x==y)continue;fa[x]=y;cnt++;res.x+=a[e[i].id];res.y+=b[e[i].id];if(cnt==n-1)break;}if(res.x*res.y<ans.x*ans.y)ans=res;else if(res.x*res.y==ans.x*ans.y&&res.x<ans.x)ans=res;return res; } void solve(point A,point B){for(ll i=1;i<=m;i++)e[i]=(node){x[i],y[i],(B.x-A.x)*b[i]+(A.y-B.y)*a[i],i};point C=Kruskal();if((C-A)*(B-A)<=0)return;solve(A,C);solve(C,B); } signed main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;i++){scanf("%lld%lld%lld%lld",&x[i],&y[i],&a[i],&b[i]);x[i]++;y[i]++;}ans.x=ans.y=1e9;for(ll i=1;i<=m;i++)e[i]=(node){x[i],y[i],a[i],i};point A=Kruskal();for(ll i=1;i<=m;i++)e[i]=(node){x[i],y[i],b[i],i};point B=Kruskal();solve(A,B);printf("%lld %lld\n",ans.x,ans.y);return 0; }

總結

以上是生活随笔為你收集整理的P5540-[BalkanOI2011]timeismoney|最小乘积生成树【最小生成树,凸壳】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。