UPC6569: Built?（最小生成树）

本文主要是介绍UPC6569: Built?（最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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≤105
0≤xi,yi≤109
All input values are integers.

 

输入

Input is given from Standard Input in the following format:

N
x1 y1
x2 y2
:
xN yN

 

输出

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.

 

样例输入

3
1 5
3 9
7 8

 

样例输出

3

 

提示

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

 

题意：给n个点，可以在任意两点之间修建道路，花费为min（|x1-x2|,|y1-y2|），问最少花费多少可以连通任意两点。

很容易可以看出这是一个最小生成树的问题，难点在于建图，

建图的话先对x排序相邻两点建条边，在对y排序相邻两点在建一条边，然后直接用最小生成树的算法就可以了。

 

#include<bits/stdc++.h> 
using namespace std;
const int L = 500005;
struct point{int xx, yy, ww;
}poi[100005];
struct node{int s, y, w;}edge[L];
int Fa[L], n, m;
void init(){for(int i = 0; i <= n; i++){Fa[i] = i;}
}
int Find(int x)//查询属于哪个集合
{if(Fa[x] == x) return x;else return Fa[x] = Find(Fa[x]);
}
void unite(int x,int y)//合并x,y两个元素
{x = Find(x);y = Find(y);if(x != y)Fa[y] = x;
}
bool same(int x, int y)//【判断是否属于同个集合
{return Find(x) == Find(y);
}
bool cmp(node a, node b)
{return a.w < b.w;
}
bool cmp1(point x, point y){return x.xx < y.xx;
}
bool cmp2(point x, point y){return x.yy < y.yy;
}int main()
{scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d%d", &poi[i].xx, &poi[i].yy);poi[i].ww = i;}m = 0;sort(poi, poi + n, cmp1);for(int i = 0; i < n; i++){if(i + 1 < n){edge[m].s = poi[i].ww;edge[m].y = poi[i + 1].ww;edge[m].w = fabs(poi[i].xx - poi[i + 1].xx);m++;}if(i - 1 >= 0){edge[m].s = poi[i].ww;edge[m].y = poi[i - 1].ww;edge[m].w = fabs(poi[i].xx - poi[i - 1].xx);m++;}}sort(poi, poi + n, cmp2);for(int i = 0; i < n; i++){if(i + 1 < n){edge[m].s = poi[i].ww;edge[m].y = poi[i + 1].ww;edge[m].w = fabs(poi[i].yy - poi[i + 1].yy);m++;}if(i - 1 >= 0){edge[m].s = poi[i].ww;edge[m].y = poi[i - 1].ww;edge[m].w = fabs(poi[i].yy - poi[i - 1].yy);m++;}}init();sort(edge, edge + m, cmp);int sum = 0, cnt = 0;for(int i = 0; i < m; i++){if(cnt == n - 1)break;if(!same(edge[i].s, edge[i].y)){unite(edge[i].s, edge[i].y);sum += edge[i].w;cnt++;}}printf("%d\n", sum);return 0;
}

 

这篇关于UPC6569: Built?（最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---