1284: 最小生成树

Memory Limit：64 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：100 Solved：14

Description

某个宇宙帝国有N个星球，由于宇宙的空间是三维的，因此每个星球的位置可以用三维坐标(X，Y，Z)来表示。任意两个不同的星球i和j都有一条边相连，边的距离是这样计算的：dis[i，j]=min(|Xi-Xj|，|Yi-Yj|，|Zi-Zj|)，其中| | 符号表示取绝对值。现在让你来挑N-1条边，让这N个星球连通成一个最小生成树，输出构成最小生成树的N-1条边的长度总和。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

  第1行，一个整数N(1≤N≤100000)。

接下来有N行，每行三个整数X，Y，Z，表示一个星球的坐标，-1000000000≤X，Y，Z≤1000000000。没有两个星球的位置完全重叠。

Output

1行，构成最小生成树的N-1条边的长度总和。

Sample Input Copy 

5
11 -15 -15
14  -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

Sample Output Copy 

4

Source/Category