正题

题目链接: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\leq n\leq 200,1\leq m\leq 10^4\)

解题思路

这种带乘积的可以维护凸壳，对于一棵生成树\(T\)我们视为一个\((\sum_{e\in T}a_e,\sum_{e\in T}b_i)\)的点，这样我们打答案一定在下凸壳上。

可以用一种分治求凸壳的方法，我们先找出下凸壳的两个端点（\(x\)最小的和\(y\)最小的）记为\(A,B\)，然后找到一个在\(A\)与\(B\)的连边下面的一个最凸的点\(C\)（可以视为最大化\(S_{\bigtriangleup ACB}\)，这样\(C\)一定在凸壳上），然后分治下去做\(\vec{AC}\)和\(\vec{CB}\)。

考虑怎么求这个\(C\)，就是最大化\(\vec{AC}\times \vec{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|最小乘积生成树【最小生成树,凸壳】

正题

题目大意

解题思路

code

最新文章

热门文章