最小生成树二·Kruscal算法(**)

zz/2024/2/25 22:17:24

最小生成树二·Kruscal算法


描述

随着小Hi拥有城市数目的增加,在之间所使用的Prim算法已经无法继续使用了——但是幸运的是,经过计算机的分析,小Hi已经筛选出了一些比较适合建造道路的路线,这个数量并没有特别的大。
所以问题变成了——小Hi现在手上拥有N座城市,且已知其中一些城市间建造道路的费用,小Hi希望知道,最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达(假设有A、B、C三座城市,只需要在AB之间和BC之间建造道路,那么AC之间也是可以通过这两条道路连通的)。
小Hi的温馨提示:边的费用在某些时候可以被理解成为边的长度、边的权值等等!所以在后文中各种可能会用上述各种称呼来描述费用一事。
小Ho听到了这个问题,发表了感慨:“这不就是之前最短路问题的时候针对点集变大,但是边集很小的稀疏图么?和SPFA算法当时遇到的问题很像诶!”
小Hi严肃道:“是的!在现实生活中,大部分的图其实都是稀疏图,哪怕不是,也可以像我这种通过筛选的方式转化为稀疏图!所以稀疏图上的问题是非常重要的!”
“是的!”小Ho连连称是,继续道:“那难道这题也像SPFA那样子来做么?但是最小生成树似乎是不可以用宽度优先搜索来解决的啊?”
“倒也没有那么复杂。”小Hi道:“还记的我们在Prim算法中得出的结论——对于城市i(i≠1),如果i与城市1的距离不超过其他任何城市j(j≠1)与城市1的距离,那么(1, i)这一条边一定存在于某一棵最小生成树中么?”
“自然记得。”
“我们来把这个结论稍微改一下:图中最短的边一定属于某棵最小生成树。”小Hi说道:“证明是简单的——因为城市1的标号是随意的,也就是无论给哪个城市标1都会有之前的结论,那么对于任意节点来说它连接的所有边中最短的边一定存在于某一棵最小生成树中,而整个图中最短的一条边一定是这样的一条边。”
小Ho道:“是的,那么也就是说我只需要不断的找到当前图中最短的一条边(一开始就将所有的边排序然后从小到大)——这样的一条边一定属于某棵最小生成树!然后我只需要将连接的2个节点合并成为一个新的节点,那么这个问题就变成了一个规模-1的问题了!只需要不断重复这样的操作,就能够使得问题最后变成1的规模,这个时候只需要之前找到的所有一定存在于最小生成树中的边的费用加起来就是答案了就可以了!”
小Hi点了点头,说道:“那么还剩一个问题,在Prim问题中,由于合并都是和1号城市合并,所以只需要简单的记录一个节点是否已经合并进了1号城市就可以了,但是在这里却会复杂很多,你有什么想法么?”
“你这就太小看我的记忆力了!”小Ho抱怨道:“在当年遇到黑叔叔的时候,我们不是学会了一种并查集的方法么?在这里只需要用并查集维护哪些节点被合并到了一起,不就行了?”
“嗯~ o( ̄▽ ̄)o,算你聪明,赶紧去实现程序吧!”
Close
输入
每个测试点(输入文件)有且仅有一组测试数据。
在一组测试数据中:
第1行为2个整数N、M,表示小Hi拥有的城市数量和小Hi筛选出路线的条数。
接下来的M行,每行描述一条路线,其中第i行为3个整数N1_i, N2_i, V_i,分别表示这条路线的两个端点和在这条路线上建造道路的费用。
对于100%的数据,满足N<=10^5, M<=10^6,于任意i满足1<=N1_i, N2_i<=N, N1_i≠N2_i, 1<=V_i<=10^3.
对于100%的数据,满足一定存在一种方案,使得任意两座城市都可以互相到达。


输出
对于每组测试数据,输出1个整数Ans,表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。


Sample Input
5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185


Sample Output
92


#include<stdio.h>
#include<algorithm>
using namespace std;
int pre[1000000];
const int INF =0x3f3f3f3f;
int n,m;
struct st
{int a,b,c;
}k[1000000];
bool cmp(st x,st y)
{return x.c<y.c;
}
void init()
{int i,j;for(i=1;i<=n;i++)pre[i]=i;
}
int find(int x)
{int r=x;while(x!=pre[x])x=pre[x];pre[r]=x;return x;
}
int main()
{scanf("%d %d",&n,&m);int ans=0;init();for(int i=1;i<=m;i++){scanf("%d %d %d",&k[i].a,&k[i].b,&k[i].c);}sort(k+1,k+1+m,cmp);for(int i=1;i<=m;i++){int x=find(k[i].a);int y=find(k[i].b);if(x!=y){ans+=k[i].c;pre[y]=x;}}printf("%d\n",ans);return 0;
}


http://www.ngui.cc/zz/2641762.html

相关文章

Crazy Search (哈希算法)

Crazy Search 给定一个字符串&#xff0c;其中含有不同的字母数量为m&#xff0c;现在求这个字符串中有多少个长度为n且长的互不相同的字符子串 举个例子, n3, m4 &#xff0c;字符串 “daababac”. 长度为3的不同的子串分别是: “daa”; “aab”; “aba”; “bab”; “bac”.…

街区最短路径问题(曼哈顿距离)

街区最短路径问题 一个街区有很多住户&#xff0c;街区的街道只能为东西、南北两种方向。 住户只可以沿着街道行走。 各个街道之间的间隔相等。 用(x,y)来表示住户坐在的街区。 例如&#xff08;4,20&#xff09;&#xff0c;表示用户在东西方向第4个街道&#xff0c;南北方…

HDU 找单词

Problem Description 假设有x1个字母A&#xff0c; x2个字母B,… x26个字母Z&#xff0c;同时假设字母A的价值为1&#xff0c;字母B的价值为2,… 字母Z的价值为26。那么&#xff0c;对于给定的字母&#xff0c;可以找到多少价值<50的单词呢&#xff1f;单词的价值就是组成一…

先验概率、后验概率、极大似然估计

先验概率 先验概率&#xff08;prior probability&#xff09;是指根据以往经验和分析得到的概率。例如投硬币事件&#xff0c;我们在执行这个事件之前就已经了解其符合二项分布&#xff0c;然后直接根据二项分布分析出的概率被称作是先验概率。它往往作为"由因求果"…

Python 网页爬虫

import re #匹配的库 import requests headers {Cookie:UM_distinctid16828a999356ee-01dbffc4bd71a8-33504275-144000-16828a99936840; CNZZDATA12553571271573548009-1546867979-%7C1546921578,Host:m.网站名称.com,User-Agent:Mozilla/5.0 (Windows NT 10.0; WOW64) Apple…

将文件数据读入结构体

将文件数据读入结构体 #include <stdio.h> #include <string.h> #include <stdlib.h> struct infostu {char no[20]; //学号 char name[20]; char sex[4];int age;char major[20]; //专业班级 }; int main() {int i0,j;struct infostu student[5…

CNN——卷积、池化与误差反向传播

卷积神经网络&#xff08;CNN&#xff09; 组成&#xff1a;输入层、卷积层、激活函数、池化层、全连接层 卷积神经网络中重要概念就&#xff1a; 深度&#xff1a;深度大小就等于所用的filter的个数[卷积层]&#xff0c;也可以理解为提取的层数。 权值共享&#xff1a;给一张…

iOS H5交互 -MUI

最近公司要求以后的项目要用iOS原生框架和h5页面结合完成,发现网上这方面的资料好少(js交互的资料是挺多的&#xff0c;我的h5页面是用MUI完成的&#xff0c;这方面的资料真的好少) 把我最近的进度做个总结 去MUI官网下载SDK 点击这里查看官方文档&#xff0c;下载SDK 下图是SD…

Hibernate配置异常

Orders和OrderItem配置 错误如图&#xff1a; 找了很久&#xff0c;才发现是因为和数据库对应的字段不同。 实体类&#xff1a; orders OrderItem xxx.hbm.xml 由于数据库对应的字段不存在itemid&#xff0c;所以图片上蓝色这一段代码应不要 数据库表格&#xff1a;

ssh+filter+cookie实现自动登陆

在ssh中&#xff0c;filter的web.xml没有正确配置的话&#xff0c;就会出现空指针异常&#xff0c;因为他执行的时候没有去找bean。也就是说filter和spring没有结合起来 实现用户自动登陆就是把用户信息保存在cookie里&#xff0c;当用户第二次访问的时候无需登陆。 实现自动…