题解 P2872 【[USACO07DEC]道路建设Building Roads】
2024-08-31 15:14:03
这道题真的是令人窒息,Kruskal调了贼久一直RE,最后发现数组大小稍微少了那么一点点。(也就10倍吧。。)
言归正传,根据本人的分析(以及算法标签的提示),这是一道求最小生成树的题目,当然要注意已经有一些路被建成了,因此他们直接标0即可。
下面是这道题用到了的所有(全局)变量。
maxn, n, m就不解释了。
x[]和y[]是用来储存农场的坐标的,当然也可以用二维数组写,只是我懒得敲那么多字(说起来差别也不大)。
f是并查集中储存祖先的数组。
如果有不了解的并查集的可以参考这一片讲解,个人认为十分通俗易懂。 传送门
f1和f2是后面暂时储存有道路连接的农场的变量。
top是Kruskal主体中记录最顶层的。
cnt是记录长度的。
ans我觉得也是废话(耶,皮这一下我很开心)。
const int maxn = ; int n, m;
int x[maxn], y[maxn], f[maxn], f1, f2;
int top = , cnt = ;
double ans = ;
接下来是储存两点距离的结构体,以及结构体排序。
struct node {
int x, y;
double val;
}dis[maxn]; bool cmp(node a, node b) {
if(a.val == b.val)
return a.x < b.x;
return a.val < b.val;
}
以及并查集模板(其中find函数使用了路径压缩)
int find(int x) {
int r = x;
while(r != f[r]) r = f[r];
int i = x, j;
while(f[i] != r) {
j = f[i];
f[i] = r;
i = j;
}
return r;
} void merge(int x, int y) {
x = find(x);
y = find(y);
if(x != y) f[y] = x;
}
偶对了还有最没用的函数dt,用于求两点距离。
double dt(int x1,int x2,int y1,int y2) {
return sqrt(pow(double(x1 - x2), ) + pow(double(y1 - y2), ));
}
接下来果断开始主函数part。
读入数据,别忘了初始化并查集。
cin >> n >> m;
for(int i = ; i <= n; i++) cin >> x[i] >> y[i];
for(int i = ; i <= n; i++) f[i] = i;
for(int i = ; i <= n; i++)
for(int j = i + ; j <= n; j++) {
dis[++cnt].x = i;
dis[cnt].y = j;
dis[cnt].val = dt(x[i], x[j], y[i], y[j]);
}
for(int i = ; i <= m; i++) {
cin >> f1 >> f2;
dis[++cnt].x = f1;
dis[cnt].y = f2;
dis[cnt].val = ;
}
然后给dis排个序。
sort(dis + , dis + cnt + , cmp);
最重要的部分:Kruskal模板
Kruskal算法将图中的每一个顶点视为一个独立的集合,首先将图中所有的边按权值大小从小到大排列,接着按顺序选择每一条边,如果这条边的两个端点不属于同一个集合,那么将它们所在的集合合并,同时将这条边加入E’。直到所有的顶点都属于同一个集合时,E’就是一颗最小生成树。
--摘抄自《ACM国际大学生程序设计竞赛 知识与入门》
for(int i = ; i <= cnt; i++) {
if(find(dis[++top].x) != find(dis[top].y)) {
ans += dis[top].val;
merge(dis[top].x, dis[top].y);
}
}
最后,愉快的输出结果就好了,别忘了要保留两位小数。
最新文章
- android Menu
- Linux 启动过程分析
- Eclipse默认标签TODO,XXX,FIXME和自定义标签[转]
- App架构设计经验谈:服务端接口的设计
- grep sed
- HDU 4614-Vases and Flowers(线段树区间更新)
- spring07 JDBC
- 怎么为WebStorm更换主题 修改字体样式
- 错误号:1364 错误信息:Field &#39;platId&#39; doesn&#39;t have a default value
- Solr搜索引擎入门知识汇总
- SQL优化一(SQL使用技巧)
- Python——Flask框架——Web表单
- PHP的核心配置详解
- vue.js购物车
- Ubuntu 安装 chrome浏览器
- Codeforces 1025 D - Recovering BST
- 【bug-劫持】深信服劫持
- MySQL Replication 详解MySQL数据库设置主从同步的方法
- PHP错误——Allowed memory size of 134217728 bytes exhausted (tried to allocate 32 bytes)
- 【vue】父向子组件传参、子组件向父传参