UPC6569: Built?(最小生成树)

2024-03-03 04:48
文章标签 最小 生成 built upc6569

本文主要是介绍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?(最小生成树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/768498

相关文章

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若