首页 > 代码库 > ARC 076 D Built 贪心+最小生成树
ARC 076 D Built 贪心+最小生成树
题意:n个点(x,y) n<=1e5,在(a,b)-(c,d)连边cost为min(|a-c|,|b-d|),任意两个点连通的最小代价?
对于两点A,B 连接两条边 权值为|a-c|,|b-d|
按x坐标排序 A,B,C三点 由于要求MST,多点联通时只可能用到相邻点的边,A-C的边不可能在MST中
所以最多2(n-1)条边,跑MST即可.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; const ll mod=1e9+7; struct node{ ll x,y,id; }a[N]; struct edge{ ll u,v,w; }e[N]; bool cmp1(node a,node b) { return a.x<b.x; } bool cmp2(node a,node b) { return a.y<b.y; } bool cmp(edge a,edge b) { return a.w<b.w; } int fa[N]; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } int main() { int n; while(cin>>n) { for(int i=1;i<=n;i++) scanf("%I64d%I64d",&a[i].x,&a[i].y),fa[i]=i,a[i].id=i; sort(a+1,a+1+n,cmp1); int cnt=0; for(int i=2;i<=n;i++) e[cnt].u=a[i].id,e[cnt].v=a[i-1].id,e[cnt++].w=abs(a[i].x-a[i-1].x); sort(a+1,a+1+n,cmp2); for(int i=2;i<=n;i++) e[cnt].u=a[i].id,e[cnt].v=a[i-1].id,e[cnt++].w=abs(a[i].y-a[i-1].y); sort(e,e+cnt,cmp); int num=n; ll ans=0; for(int i=0;i<cnt;i++) { int u=e[i].u,v=e[i].v; int fx=find(u),fy=find(v); if(fx!=fy) { ans+=e[i].w; fa[fx]=fy; num--; if(num==1) break; } } cout<<ans<<endl; } return 0; }
ARC 076 D Built 贪心+最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。