首页 > 其他分享 >【笔记/模板】最小生成树

【笔记/模板】最小生成树

时间:2024-11-04 10:32:34浏览次数:1  
标签:dist int rhs 最小 笔记 生成 权值 return 模板

www.luogu.com.cn

概念/定义

一个连通图的生成树是一个极小的连通子图,它包含图中全部的 \(n\) 个顶点,但只有构成一棵树的 \(n-1\) 条边。而最小生成树就是一个带权图的生成树,并且使得原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

思路(Kruskal适用于稀疏图,Prim适用于稠密图)

Kruskal 算法

整体思路:

Kruskal 是一种使用贪心 + 排序+并查集的最小生成树算法,通过每两个点之间的最小距离累加并且将两个点合并,最终生成一种生成树的算法。

时间复杂度:

\(O(m \log m)\)(其中 \(m\) 点表示边数)。

代码实现:

struct Edge
{
	int u, v, w; // 存下入边,出边,权值
	bool operator < (const Edge &rhs) const // 重载运算符,将权值为第一关键词非降序排序
	{
		if (w != rhs.w) return w < rhs.w;
		if (u != rhs.u) return u < rhs.u;
		return v < rhs.v;
	}
};
vector <Edge> graph;
int pre[N];

int rt(int x)
{
	return pre[x] = (pre[x] == x ? x : rt(pre[x]));
}

inline void merge(int x, int y)
{
	pre[rt(x)] = rt(y);
}

inline bool check(int x, int y)
{
	return rt(x) == rt(y);
}
int main()
{
	// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m; cin >> n >> m;
	
	for (int i = 1; i <= m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		graph.push_back({u, v, w}); // 存边
	}
	sort(graph.begin(), graph.end()); // 排序
	
	ll ans = 0;
	for (int i = 1; i <= n; i++) pre[i] = i; // 并查集初始化
  
	for (auto t : graph)
	{
        auto &[a, b, val] = t;
		if (check(a, b)) continue; // 如果已经联通,则跳过
		ans += val; // 直接加上这两条边的权值
		merge(a, b); // 合并该两条边
	}
	
	bool tag = true;
	for (int i = 1; i < n; i++)
		if (rt(i) != rt(i + 1)) tag = false; // 判断是否可以形成连通图
	if (tag == false) cout << "orz\n";
	else cout << ans;
		
	return 0;
}

Prim 算法

整体思路:

Prim 的思想是将任意节点作为根,再找出与之相邻的所有边中最短的一条边,再将新节点更新并以此节点作为根继续搜,同时维护一个数组作用为已用点到未用点的最短距离,并且一个 \(bool\) 数组来记录没有存入生成树的边。实现操作类似 Dijkstra 算法。

核心思路:对于任意一个顶点 \(v\),连接到该顶点的所有边中的一条最短边必然属于最小生成树。

时间复杂度:

朴素:\(O(n^2)\),堆优化:\(O(n \log n)\)(其中 \(n\) 表示点数)。

代码实现:

struct Edge
{
	int ver, val;
	bool operator < (const Edge &rhs) const { return val > rhs.val; }
};
void prim()
{
	memset(dist, 0x3f, sizeof dist);	// 将 dist 数组初始化为无穷大
	bitset<N> intree;
	priority_queue<Edge> heap;
	
	heap.push({1, 0});	// 先将第一个点加入队列当中
	dist[1] = 0;
	
	while (!heap.empty())
	{
		auto [ver, val] = heap.top(); heap.pop();	//取出队列当中最短的一个边
		
		if (intree[ver]) continue;
		intree[ver] = true;
		
		ans += val;	// 加上权值并且标记掉
		
		for (int i = h[ver]; ~i; i = ne[i])	// 遍历该点的所有出点
		{
			int j = e[i];
			if (!intree[j] && w[i] < dist[j])	// 如果存在没有标记且离该点更近的点 
				dist[j] = w[i], heap.push({j, w[i]});	// 更新dis数组 将这个点加入队列当中
		}
	}
	
	bool tag = true;	// 判断是否可以形成连通图
	for (int i = 1; i <= n; i++) if (!intree[i]) tag = false;
	if (tag == true) cout << ans << '\n';
	else cout << "orz\n";
}

标签:dist,int,rhs,最小,笔记,生成,权值,return,模板
From: https://www.cnblogs.com/ThySecret/p/18523428

相关文章

  • 【模板】Floyd算法
    Floyd算法原理Floyd算法用来求出任意两个节点之间的最短路。优点:代码少,思维简单,适用于除了负环以外的任何图。缺点:时间复杂度为\(O(n^3)\),空间复杂度为\(O(n^2)\)。而Floyd的核心原理是用动态规划实现的,定义一个二维数组\(f_{i,j}\),遍历图上的所有点\(k\),可以得......
  • 【模板】分块
    今天写分块的时候模板忘光了,故写以记之。CodeInitvoidinit(){sz=sqrt(n),block=n/sz+(n%sz!=0);for(inti=1;i<=block;i++)st[i]=(i-1)*sz+1,ed[i]=i*sz;ed[block]=n;for(inti=1;i<=block;i++)......
  • PbootCMS模板调用友情链接标签代码
    适用范围:全站任意地方标签作用:用于依次输出指定分组的友情链接调用代码:html {pboot:linkgid=*num=*}<ahref="[link:link]"title="[link:name]"><imgsrc="[link:logo]"></a>{/pboot:link}控制参数:gid=*:分组,必填num=*:数量,非必填,默认为10个可使用的列表......
  • PbootCMS模板调用幻灯片轮播图标签
    幻灯片轮播图列表:{pboot:slidenum=3gid=1}<ahref="[slide:link]"target="_blank"><imgsrc="[slide:src]"alt="[slide:title]"/></a>{/pboot:slide}控制参数:gid=*:分组,必填。num=*:数量,非必填,默认为5个。可用列表标......
  • pbootcms模板英文站搜索效果页面包屑显示优化
    打开 \apps\home\controller\SearchController.php 文件,根据版本替换代码:2.1.1版本:if(cookie('lg')=='cn'){//中文处理}else{//英文处理$content=str_replace('{pboot:pagetitle}',$this->config('search_title')?:......
  • GD32F1x模板工程的创建
    本文根据b站up主高博士_嵌入式的视频来写。视频链接:[2-3]05创建GD32F10x模板工程_哔哩哔哩_bilibili第一章:项目的创建首先创建一个文件夹,这个文件夹用来储存项目。  我们把项目的名字命名为test。  选择自己要使用的芯片,点击ok。 点击三个方块形状形成的按钮出......
  • Web 靶场笔记-bWAPP
    事以密成,言以泄败。导航前言A1-Injection(注入)A2-BrokenAuth&SessionMgmt(破损的授权&会话管理)A3-Cross-SiteScripting(XSS跨站脚本)A4-InsecureDirectObjectReferences(IDOR不安全直接对象引用)A5-SecurityMisconfiguration(安全配置错误)......
  • 《人件集》阅读笔记2(2024.11.1)
    一、章节内容梳理(一)第五章:环境与协作的交织这一章让我深刻认识到办公环境对软件开发人员的重要性。无论是物理空间的布局,还是设施的配备,都如同隐形的手影响着工作效率和团队沟通。从开发人员的角色定位角度看,合适的环境能让他们更清晰地明确自己在团队中的位置,更好地发挥专长。......
  • FFT学习笔记
    $\quad$本人蒟蒻,只能介绍FFT在OI中的应用,如有错误或不当之处还请指出。$\quad$首先先说一下那一堆什么什么\(TT\)的都是什么DET:离散傅里叶变换用于求多项式乘法\(O(n^2)\)FFT:快速傅里叶变换用于求多项式乘法\(O(nlog(n))\)FNTT/NTT:FTT的优化,常数及精度更优FWT......
  • matlab学习笔记:第四章程序流程控制(总)
    4.1条件语句 4.1.1if-elseif-else-end语句易错点:elseif关键字中间不能加空格,不能写成elseif,这和C、Java等语言不同。注意:在使用if语句时,if和end这两个关键字是无论如何都不能省略的。而elseif和else可以根据自己的需要来决定是否添加。如果if和elseif后面表达式的计算结......