首页 > 其他分享 >最小生成树

最小生成树

时间:2022-08-26 20:23:27浏览次数:54  
标签:cnt prim int 最小 生成 edge 起点

最小生成树主要应用:

举个例子,两个城市需要光缆联通,且两个城市安装光缆有一定价格,任意两个城市必须联通,求最小价格

这时候就需要运用到最小生成树,当然这个题只是需要套模板,有些变种:https://www.luogu.com.cn/problem/P1195  这道题也是最小生成树,换汤不换药

最小生成树有2种算法:prim和Kruskal

Kruskal:

这个相对比较容易理解,就是将所有边取出来放入一个列表,并且放入时要排序从小到大(用贪心的思想优先选取权值较小的边)。在这之后,就往图中填边。在填边的过程中注意,如果他构成了一个环,舍弃这条边(用并查集来判断是否存在环)(因为如果构成环肯定已经联通,再加入就是多余的),否则就计数器++(计数器是记录填入边的数量),如果到n-1就终止循环,过程中再ans(=0)再加上填入边的权值就可以了QAQ

上图为Kruskal的图,将左边列表依次加入就行了!

#include<bits/stdc++.h>	//万能头

using namespace std;

int n , m ,fa[50005],cnt,ans,flag;//n个点,m条边,并查集判断环 ,cnt为加入边数 
struct node{
	int u,v,w;
}edge[200005];//意义不明的存边 

bool cmp(node a,node b)
{
	return a.w < b.w;
}//排序依据,从小到大 

int find(int x)
{
	if(fa[x] == x)
		return x;
	else 
		return fa[x] = find(fa[x]);//递归+状态压缩 实现并查集的‘查’ 
}

void merg(int a,int b)
{
	int x = find(a),y = find(b);
	if(x==y)
		return;
	else
		fa[x] = y;//合并函数 
}

int main()
{
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++)
		fa[i] = i;//初始化并查集 
	for(int i = 1 ; i <= m ;  i++)
		cin >>edge[i].u >> edge[i].v >> edge[i].w;//虽然无向图但不影响 
	sort(edge+1,edge+m+1,cmp);
	for(int i = 1 ; i <= m ;  i++)
	{
		int a = edge[i].u,b = edge[i].v,c = edge[i].w;
		if(cnt == n-1)
		{
			break;//如果已经加入了n-1条边,直接跳出 
		}
		if(find(a)==find(b))
			continue;//如果已经联通跳出进行下一次;
		ans += c;
		cnt++;
		merg(a,b);
	}
	if(cnt!=n-1)//判断是否不连通 
		cout<<"orz";
	else
		cout<<ans;

} 

 

 亲自手打代码+详细注释

prim:

所谓prim和最短路的dijkstra非常接近,只是目的不同,首先以0为起点,遍历起点为0的边,如果边的v(初始全部为inf)要小于从起点距离+权值就替换,类似蓝白点,标记0,再选一个最小的作为起点

1.更新(以起点为出发点,更新所连接点的距离(初始为正无穷inf))

2.扫描(扫描距离最小的点并且未被标记,将其作为下一次的起点)

3.创建(以扫描到的起点为出发点,重复上述操作,直到覆盖完全部的点)

如果还是看不懂推荐去看这个视频:https://www.bilibili.com/video/BV1Eb41177d1?spm_id_from=333.337.search-card.all.click&vd_source=5f02dc5b35066015d1aef125eacf7273

接下来代码贴上:

#include <bits/stdc++.h>//万能头 
#define inf 0x3f3f3f

using namespace std;

int n,m,cnt,ans,dis[400005],vit[400005],now = 1,tot,minn,head[400005],flag;
struct edge{
	int v,w,nxt;
}e[400005];

void add(int u,int v,int w)
{
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
} //链式前向星存图 ,方便后面遍历边 
 
void prim()//噩梦开始的地方 
{
	for(int i = 2 ; i <= n ; i++)
		dis[i] = inf;//将除了起点之外的点的距离初始化为正无穷 
	for(int i = head[1];i;i = e[i].nxt)
	{
		dis[e[i].v] = min(dis[e[i].v],e[i].w);
	}//遍历起点1能到达的点 
	while(++tot<n)//for循环也可以吧 
	{
		minn = inf;//找最小值,赋为最大 
		vit[now] = 1;//将现在的点标记一下,也就是起点 
		for(int i = 1 ; i <= n ; i ++)
		{
			if(!vit[i]&&minn>dis[i])
			{
				minn=dis[i];
				now = i;
			}	
		}//找没被标记的最小值 
		if(vit[now])
		{
			flag = 1;
			return;
		}//如果还是被标记了说明压根没找到,图不连通,返回		 
		ans += minn;//加上到这个点的边的长度 
		for(int i = head[now];i;i = e[i].nxt)
		{
			if(!vit[e[i].v]&&dis[e[i].v]>e[i].w)
			{
				dis[e[i].v] = e[i].w;
			}
		}//从这个起点更新其他未被标记点 
	}
 } 


int main()
{
	cin >> n >> m;//n个点,m条边
	for(int i = 1; i <= m ; i ++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		add(x,y,z);
		add(y,x,z);
	}//无向图,建图 
	prim();
	if(flag)	
	{
		cout<<"orz";
		return 0;
	}//无联通 
	
	
	printf("%d", ans);
	return 0;
} 

  

 prim多用于稠密图,Kruskal多用于稀疏图,比赛时看清数据范围

最后:

 

标签:cnt,prim,int,最小,生成,edge,起点
From: https://www.cnblogs.com/fk-thank/p/16629061.html

相关文章

  • 生成随机数
    publicstaticvoidmain(String[]args){Randomrandom=newRandom();random.ints(-100,100).limit(10)/......
  • PHP 生成随机中文汉字 gb2312转utf8
    学习记录留作参考祝君好运参考:信息交换用汉字编码字符集基本集GB/T2312-1980有些情况下需要生成一些随机汉字,参考了一些网上一些方法,感觉有些模糊。于是找到了g......
  • 使用matlab生成正弦波、三角波、方波
    生成余弦波数据(该示例中展示了如何输出十六进制数据到文件中)N=100;y=zeros(N,1);%生成100行*1列的矩阵y_integer=zeros(N,1);%生成100行*1列的矩阵y_h......
  • 最小二乘法(least sqaure method)
    文章结构如下:1:最小二乘法的原理与要解决的问题2:最小二乘法的矩阵法解法3:最小二乘法的几何解释4:最小二乘法的局限性和适用场景5:案例python实现6:参考文献1......
  • geopandas 生成 shp 文件
    生成shp文件ss=[]forilinC.allsegs[1:5]:ss.append(geometry.MultiLineString([i.tolist()foriiniliflen(i.tolist())>1]))cq=geopandas.GeoD......
  • xarray 生成 tiff 文件
    生成tiff文件fromeccodesimport*importnumpyasnpimportxarrayasxrimportrioxarrayasriot2=xr.Dataset(data_vars={'REF':(['longitude','latit......
  • 最小化安装killall不可用
    最小化安装killall不可用最小化安装Centos7.4后,发现killall命令不可用 使用了以下命令,查看软件包名:yumsearchkillall 查找后发现应使用这个安装包yum-yinsta......
  • Python基础——迭代器 生成器
    迭代器iterator迭代简单理解就是重复,但是每次重复产生的结果还要作为下次重复的初始值。可迭代对象:含有——iter——方法的对象。可以用for...in..遍历的都是可迭代对......
  • 三个数的最小公倍数
    扩大倍数法(代码实现容易)先列举出这三个数中最大数的倍数,再从这些倍数中找出较少数的倍数,即这两个数的公倍数,从而确定出最小公倍数。枚举法与求两个数的最小公倍数方......
  • 如何利用configure.ac和Makefile.am生成Makefile
    环境是Ubuntu18.041、aclocal命令根据configure.ac文件的内容,自动生成aclocal.m4文件。 2、autoconf命令会根据configure.ac和aclocal.m4文件,生成configure文件。  ......