Moo Network

题目描述

农夫约翰的 $N$ 头奶牛（$1 \leq N \leq 10^5$）分散在他的农场各处，它们希望建立一个通信网络，以便更容易地交换电子短信（当然内容都是各种“moo”的变体）。第 $i$ 头奶牛位于一个互不相同的位置 $(x_i,y_i)$，其中 $0 \leq x_i \leq 10^6$ 且 $0 \leq y_i \leq 10$。在奶牛 $i$ 与奶牛 $j$ 之间建立一条通信连接的代价为它们之间距离的平方：$(x_i-x_j)^2 + (y_i-y_j)^2$。 请计算建立一个使所有奶牛都能互相通信的通信网络所需的最小总成本。两头奶牛可以通信，当且仅当它们之间直接由一条连接相连，或存在一条由若干连接组成的路径使得消息可以沿其传递。 注意：本题时间限制为 4s，是默认值的两倍。

输入格式

第一行输入包含 $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

提示

SCORING: 测试点 2-3 满足 $N \le 1000$。 测试点 4-15 没有额外限制。 题目来源：Brian Dean

标签: USACO|2022|Gold

来源

USACO|2022|Gold