P6969: 通信网络
传统题
4.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
Farmer John
的 N
头奶牛（1≤N≤10^5
）在他的农场里分散得很远，她们想建立一个通信网络，从而她们可以更容易地互相发送电子文本信息（当然所有信息包含的都是各种各样的「哞」）。
第 i
头奶牛位于各不相同的位置 (xi,yi)，其中 0≤xi≤10
^6
以及 0≤yi≤10。在奶牛 i
和 j 之间建立通信连接的花费是它们之间的平方距离：(xi−xj)^2+(yi−yj)
^2
。
请计算建立所有奶牛可以互相通信的通信网络所需的最小花费。当两头奶牛之间存在直接的通信连接，或存在一系列通信连接可以传递她们的信息，则这两头奶牛之间可以通信。
**
注意：本题的时间限制为 4 秒，通常限制的两倍。**
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
，以下 N
行每行包含一头奶牛的 x 和 y，均为整数。
【
输出格式】
（输出至终端 /
标准输出）：
输出可以使得所有奶牛可以互相通信的通信网络的最小花费。注意这个花费可能无法使用 32
位整数型存储，可能需要使用 64 位整数型（例如，C++ 中的 "long long"）。
【
输入样例】
：
10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0
【
输出样例】
：
660
【
测试点性质】
：
测试点 2-3
满足 N≤1000。
测试点 4-15
没有额外限制。