首页 技术 正文
技术 2022年11月23日
0 收藏 465 点赞 4,729 浏览 1320 个字

概念

一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。 [1] 最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。

通俗一点,就是把一个图,削成一个树,要让这颗树权值最小

思路(kruskal)

kruskal算法的基本思路就是,把所有的边以权值为关键字排序,然后,依次将一个一个点放入最小生成树中
如果,这个点已经有了,那我们就直接跳过 是不是很简单
因为搜索是否已经放入可以用dfs或bfs来查找,这样的时间很长,所以,要使用并查集,就是把最小生成树的每一个结点放入一个并查集,可以更加简便地查找
*** 必需是连通图 ***

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。

输入格式
第一行包含两个整数 N,MN,M,表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 X_i,Y_i,Z_iX


表示有一条长度为 Z_iZ

的无向边连接结点 X_i,Y_iX
输出格式
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例
输入 #1复制
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出 #1复制
7
说明/提示
数据规模:

对于 20%20% 的数据,N\le 5N≤5,M\le 20M≤20。

对于 40%40% 的数据,N\le 50N≤50,M\le 2500M≤2500。

对于 70%70% 的数据,N\le 500N≤500,M\le 10^4M≤10

对于 100%100% 的数据:1\le N\le 50001≤N≤5000,1\le M\le 2\times 10^51≤M≤2×10

所以最小生成树的总边权为 2+2+3=72+2+3=7。

题目分析

最小生成树模板题

代码

#include<bits/stdc++.h>
using namespace std;
int fa[5005];
int n;
int m;
int x,y,e;
int tot=0;
int ans=0;
bool flag=1;
struct edge{
int u,v,w;
}g[200005];
bool cmp(edge x,edge y)
{
return x.w<y.w;
}
void Make()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
return ;
}
int find(int x)
{
if(fa[x] == x)
return x;
else
return find(fa[x]);
}
void unionn(int i, int j)
{
fa[find(i)] = find(j);
return ;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&e);
g[i].u=x;
g[i].v=y;
g[i].w=e;
}
sort(g+1,g+1+m,cmp);
Make();
for(int i=1;i<=m;i++)
{if(find(g[i].u)!=find(g[i].v))
{
unionn(g[i].u, g[i].v);
tot++;
ans+=g[i].w;
}
if(tot==n-1)
{
break;
}
}printf("%d",ans);
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141344.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:7,097
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,454
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:566 阅读:5,265
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,147
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,314
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,859