问题 B: 最小生成树
传统题
1.000s
时间限制
64MB
内存限制
8 提交
2 解决
【题目描述】
某个宇宙帝国有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