高端网站设计公司如何设计网站,谷歌seo关键词优化,广告毕业设计作品网站,宁波网站推广营销正题
题目链接:https://www.luogu.com.cn/problem/P5540 题目大意
给出nnn个点mmm条边边权是一个二元组(ai,bi)(a_i,b_i)(ai,bi)#xff0c;求出一棵生成树最小化 (∑e∈Tae)(∑e∈Tbe)(\sum_{e\in T}a_e)\times(\sum_{e\in T}b_e)(e∈T∑ae)(e∈T∑be) 的情况下…正题
题目链接:https://www.luogu.com.cn/problem/P5540 题目大意
给出nnn个点mmm条边边权是一个二元组(ai,bi)(a_i,b_i)(ai,bi)求出一棵生成树最小化 (∑e∈Tae)×(∑e∈Tbe)(\sum_{e\in T}a_e)\times(\sum_{e\in T}b_e)(e∈T∑ae)×(e∈T∑be) 的情况下最小化∑e∈Tae\sum_{e\in T}a_e∑e∈Tae
1≤n≤200,1≤m≤1041\leq n\leq 200,1\leq m\leq 10^41≤n≤200,1≤m≤104 解题思路
这种带乘积的可以维护凸壳对于一棵生成树TTT我们视为一个(∑e∈Tae,∑e∈Tbi)(\sum_{e\in T}a_e,\sum_{e\in T}b_i)(∑e∈Tae,∑e∈Tbi)的点这样我们打答案一定在下凸壳上。
可以用一种分治求凸壳的方法我们先找出下凸壳的两个端点xxx最小的和yyy最小的记为A,BA,BA,B然后找到一个在AAA与BBB的连边下面的一个最凸的点CCC可以视为最大化S△ACBS_{\bigtriangleup ACB}S△ACB这样CCC一定在凸壳上然后分治下去做AC⃗\vec{AC}AC和CB⃗\vec{CB}CB。
考虑怎么求这个CCC就是最大化AC⃗×CB⃗\vec{AC}\times \vec{CB}AC×CB (xC−xA)(yB−yA)−(xB−xA)(yC−yA)(x_C-x_A)(y_B-y_A)-(x_B-x_A)(y_C-y_A)(xC−xA)(yB−yA)−(xB−xA)(yC−yA) xC(yB−yA)−yC(xB−xA)yA(xB−xA)−xA(yB−yA)x_C(y_B-y_A)-y_C(x_B-x_A)y_A(x_B-x_A)-x_A(y_B-y_A)xC(yB−yA)−yC(xB−xA)yA(xB−xA)−xA(yB−yA) 然后就是相当于最小化xC(yB−yA)yC(xA−xB)x_C(y_B-y_A)y_C(x_A-x_B)xC(yB−yA)yC(xA−xB)拿这个当边权跑就可以跑出CCC了。
然后时间复杂度据说是O(mlogmlnn!)O(m\log m\sqrt{\ln n!})O(mlogmlnn!) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const int N210,M1e410;
struct node{ll x,y,w,id;
}e[M];
struct point{ll x,y;point(ll xx0,ll yy0){xxx;yyy;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.wy.w)?(a[x.id]a[y.id]):(x.wy.w);}
ll find(ll x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
point Kruskal(){ll cnt0;point res0;for(ll i1;in;i)fa[i]i;sort(e1,e1m,cmp);for(ll i1;im;i){ll xfind(e[i].x),yfind(e[i].y);if(xy)continue;fa[x]y;cnt;res.xa[e[i].id];res.yb[e[i].id];if(cntn-1)break;}if(res.x*res.yans.x*ans.y)ansres;else if(res.x*res.yans.x*ans.yres.xans.x)ansres;return res;
}
void solve(point A,point B){for(ll i1;im;i)e[i](node){x[i],y[i],(B.x-A.x)*b[i](A.y-B.y)*a[i],i};point CKruskal();if((C-A)*(B-A)0)return;solve(A,C);solve(C,B);
}
signed main()
{scanf(%lld%lld,n,m);for(ll i1;im;i){scanf(%lld%lld%lld%lld,x[i],y[i],a[i],b[i]);x[i];y[i];}ans.xans.y1e9;for(ll i1;im;i)e[i](node){x[i],y[i],a[i],i};point AKruskal();for(ll i1;im;i)e[i](node){x[i],y[i],b[i],i};point BKruskal();solve(A,B);printf(%lld %lld\n,ans.x,ans.y);return 0;
}
