1824: 最小生成树
内存限制:64 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
某个宇宙帝国有N个星球,由于宇宙的空间是三维的,因此每个星球的位置可以用三维坐标(X,Y,Z)来表示。任意两个不同的星球i和j都有一条边相连,边的距离是这样计算的:dis[i,j]=min(|Xi-Xj|,|Yi-Yj|,|Zi-Zj|),其中| | 符号表示取绝对值。现在让你来挑N-1条边,让这N个星球连通成一个最小生成树,输出构成最小生成树的N-1条边的长度总和。
输入
第1行,一个整数N(1≤N≤100000)。
接下来有N行,每行三个整数X,Y,Z,表示一个星球的坐标,-1000000000≤X,Y,Z≤1000000000。没有两个星球的位置完全重叠。
输出
1行,构成最小生成树的N-1条边的长度总和。
样例输入 复制
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
样例输出 复制
4