博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Kruskal HDOJ 1233 还是畅通工程
阅读量:6735 次
发布时间:2019-06-25

本文共 1464 字,大约阅读时间需要 4 分钟。

 

1 /* 2     最小生成树之kruskal算法--并查集(数据结构)实现 3     建立一个结构体,记录两点和它们的距离,依照距离升序排序 4     不连通就累加距离,即为最小生成树的长度 5 */ 6 #include 
7 #include
8 #include
9 #include
10 using namespace std;11 12 const int MAXN = 5e3 + 10;13 const int INF = 0x3f3f3f3f;14 int rt[MAXN];15 struct Node16 {17 int u, v, w;18 }node[MAXN];19 20 bool cmp(Node x, Node y) {
return x.w < y.w;}21 22 int Find(int x) {
return (rt[x] == -1) ? x : rt[x] = Find (rt[x]);}23 24 void Union(int x, int y)25 {26 x = Find (x); y = Find (y);27 if (x > y) rt[y] = x;28 else if (x < y) rt[x] = y;29 }30 31 bool same(int x, int y) {
return (Find (x) == Find (y));}32 33 int main(void) //HDOJ 1233 还是畅通工程34 {35 //freopen ("inB.txt", "r", stdin);36 int n, m;37 38 while (~scanf ("%d", &n) && n)39 {40 m = n * (n - 1) / 2;41 memset (rt, -1, sizeof (rt));42 for (int i=1; i<=m; ++i)43 {44 scanf ("%d%d%d", &node[i].u, &node[i].v, &node[i].w);45 }46 sort (node+1, node+1+m, cmp);47 int sum = 0;48 for (int i=1; i<=m; ++i)49 {50 int x = node[i].u; int y = node[i].v;51 int w = node[i].w;52 if (!same (x, y)) {Union (x, y); sum += w;}53 }54 printf ("%d\n", sum);55 }56 }

 

转载于:https://www.cnblogs.com/Running-Time/p/4512994.html

你可能感兴趣的文章
HDFS配额
查看>>
ceph - pg 常见状态
查看>>
Linux 命令大全
查看>>
HttpClient——概述(一)
查看>>
初探ECMAScript6
查看>>
我的MYSQL学习心得(一) 简单语法
查看>>
加速scp传输速度
查看>>
MAC MAMP php安装memcache扩展安装方法
查看>>
异步与回调
查看>>
Electron入门教程
查看>>
通读ES6--数值的扩展
查看>>
Flink实时计算性能分析
查看>>
参加51CTO学院软考培训,我通过啦
查看>>
阿里云梁楹:这样的青春,别样的精彩
查看>>
Pandas - 快速入门
查看>>
通过java流实现读取文件
查看>>
Log4j 基本使用
查看>>
ssh 通过sshpass自动登录远程主机
查看>>
Eclipse/MyEclipse 常用的快捷键
查看>>
wordpress获取当前分类下的子分类
查看>>