GDUT

2023-03-14 12:28| 来源: 网络整理| 查看: 265

题目描述：

There are N towns on a plane. The i-th town is located at the coordinates (xi,yi). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(∣a−c∣,∣b−d∣) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2≤N≤1050≤xi,yi≤109All input values are integers.

Input

Input is given from Standard Input in the following format:

N 1x1 1y1 2x2 2y2 : xN yN

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample 1

InputcopyOutputcopy 3 1 5 3 9 7 8 3

Build a road between Towns 11 and 22, and another between Towns 22 and 33. The total cost is 2+1=32+1=3 yen.

Sample 2

InputcopyOutputcopy 6 8 3 4 9 12 19 18 1 13 5 7 6 8 思路：

这道题用到kruscal算法，先求y轴的距离并排序填入数组中，再求x轴的距离并排序填入上同一个数组中，最后在对数组排序，从小到大联通城市。

代码： #include #include #include #include #include #include using namespace std; typedef long long ll; typedef double db; struct point{ int x,y,id; }a[100005]; struct edge{ int p1,p2,len; }ans[200005]; int idx[100005]; bool cmpx(point a,point b){ return a.x>a[i].y; a[i].id=i; } sort(a+1,a+1+n,cmpx); for(int i=1;i

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章