P8074 [COCI2009-2010#7] SVEMIR

题目描述

太空帝国要通过建造隧道来联通它的 NN 个星球。

每个星球用三维坐标 (x,y,z) 来表示，而在两个星球 A,B 之间建造隧道的价格为 min{|xA-xB|,|yA-yB|,|zA-zB|}。

现要建造N−1 条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。

输入格式

第一行，一个整数 N。

接下来的 N 行，每行三个整数 x,y,z，表示第 ii 个星球的坐标。

数据保证不存在两个具有相同坐标的星球。

输出格式

输出所需的最小总价。

• 对于100% 的数据，1 <= N <=10^5,-10^9 <= x,y,z<=10^9。

思路

一眼就是最小生成树，但是需要自己建边，每两个星球之间都可以建边，但要都建吗？显然是错误的（会MLE），考虑排除那些冗余的边（对答案没有贡献）。

假设三个星球的位置x为0,1,2，那想一想我们需要建第一个星球和第三个星球的路吗？显然不用，因为我们建第一个和第二个＋第二个和第三个更优。

于是我们考虑将x,y,z坐标分别从小到大排序，只建相邻两个星球的边，这样边的数量最多也就300000条。然后最小生成树模板。

Code

#include
#include
#include 
#include
using namespace std;
inline int read(){int w=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}return w*f;
}
int n,tot,cnt,f[100005];
long long ans;
struct pla{int x;int y;int z;int id;
}p[100005];
struct edge{int u;int v;int dis;
}g[300005];
int get(int x){if(f[x]==x) return x;else f[x]=get(f[x]); 
}
void merge(int x,int y){f[x]=y;
}
bool cmp1(pla a,pla b){return a.x

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！