poj2031 kruskal
2023-03-14 10:16:36 时间
http://poj.org/problem?id=2031
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; double a[101][4]; double esp = 0.0000001; struct edge { int u,v; double w; } e[5000]; int tree[101]; int cmp( const void *a ,const void *b) { return (*(edge *)a).w > (*(edge *)b).w ? 1 : -1 ; } int main() { int n; //freopen("1.txt","r",stdin); while (cin>>n,n) { int i,j; for (i = 0; i < n; ++i) cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3]; int k = 0; for (i = 0; i < n-1; ++i) for (j = i+1; j < n; ++j) { e[k].u = i; e[k].v = j; double temp = sqrt( (a[i][0]-a[j][0])*(a[i][0]-a[j][0]) +(a[i][1]-a[j][1])*(a[i][1]-a[j][1]) +(a[i][2]-a[j][2])*(a[i][2]-a[j][2]) )- a[i][3] - a[j][3]; if (temp < esp) e[k].w = 0; else e[k].w = temp; ++k; } qsort(e,k,sizeof(e[0]),cmp); for (i = 0; i < n; ++i) tree[i] = i; double total = 0; for (i = 0; i < k; ++i) { int m1 = tree[e[i].u]; int m2 = tree[e[i].v]; if (m1 != m2) { total += e[i].w; for (j = 0; j < n; ++j) if (tree[j] == m2) tree[j] = m1; } } printf("%.3f\n",total); } return 0; }
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的