首页 > 编程语言 >算法笔记-生成树

算法笔记-生成树

时间：2023-10-09 15:12:13浏览次数：47  
标签：连通 val int 笔记 生成 fa 算法 Maxn

概念定义

图：由点和边组成的集合

生成图：图中删去若干个点和若干条边后剩下的子图

生成树：恰好为树的生成图

最小生成树：边权总和最小的生成树

严格次小生成树：边权总和严格大于最小生成树且最小

 

最小生成树

Kruskal

Kruskal 是通过贪心法选边加入集合来求最小生成树的算法

 

算法过程

  • 把所有的点加入集合
  • 把所有的边按边权递增排序
  • 遍历每一条边，如果边的两个端点不连通，将此边加入集合，两个端点所在连通块合并
  • 重复 2, 3 步，直到所有点同属一个连通块

 

证明及实现

　感性的理解一下，我们最终要选择 n - 1 条边加入集合，那么肯定要选择边权尽可能少的。

　在第 3 步时，如果我们不选目前这条边，为了使两个连通块连通，一定会更劣，所以选择这条边就是最优的。

　实现的话，我们需要排序，为了维护连通块，还需要并查集。

　时间复杂度  O(M log M)

 

代码示例

#include <bits/stdc++.h>

using namespace std;
const int Maxn = 5e3 + 7, Maxm = 2e5 + 7;

struct Edge { int fro, to, val; }e[Maxm];
int N, M, ans, fa[Maxn], tot;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }//并查集

int main() { ios::sync_with_stdio(false);
	
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) fa[i] = i; tot = N;
	for (int i = 1; i <= M; ++i) cin >> e[i].fro >> e[i].to >> e[i].val;
	
	sort(e + 1, e + 1 + M, [](const Edge& x, const Edge& y){ return x.val < y.val; });//按边权递增排序
	
	for (int i = 1; i <= M; ++i) {
		int u = e[i].fro, v = e[i].to;
		if ((u = find(u)) == (v = find(v))) continue;
		fa[u] = v, --tot, ans += e[i].val;//端点不在一个连通块，合并
		if (tot == 1) { cout << ans << '\n'; return 0; }//只剩一个连通块，输出
	}
	
	puts("orz");//原图不连通，无解
	return 0;
}

Luogu P3366

　

Prim

Prim 是通过选点及其某一连边不断加入集合来求最小生成树的算法。

 

 算法过程

  • 将一个点加入集合
  • 将与集合中点连边权值最小的一个点及连边加入集合
  • 重复第 2 步，直到所有点都被加入集合

 

证明

　

红色的边已加入最小生成树

　　

显然整张图每次被分为了集合内的点和非集合内的点，两个部分之间不连通。

那么使两个部分连通的最小代价就是两个部分之间的连边中权值最小的。

重复此过程求得的解显然是最优的。

 

代码示例

 

#include <bits/stdc++.h>

using namespace std;
const int Maxn = 5e3 + 7, Maxm = 4e5 + 7;

struct Edge { int nxt, to, val; }e[Maxm]; int head[Maxn], cnte;
int N, M, ans, dis[Maxn]; bool in[Maxn];

inline void add(int u, int v, int w) { e[++cnte] = (Edge){ head[u], v, w }; head[u] = cnte; }

int main() { ios::sync_with_stdio(false);
	
	cin >> N >> M;
	for (int i = 1, u, v, w; i <= M; ++i)
		cin >> u >> v >> w, add(u, v, w), add(v, u, w);
	
	memset(dis, 0x3f, sizeof(dis)); dis[1] = 0;
	
	for (int k = 1; k <= N; ++k) {
		int u = -1, mi = 0x3f3f3f3f3f;
		for (int i = 1; i <= N; ++i)
			if (!in[i] and dis[i] < mi) mi = dis[i], u = i;
		if (u == -1) { puts("orz"); return 0; }
		
		ans += dis[u], in[u] = true;
		
		for (int i = head[u]; i ; i = e[i].nxt) { int v = e[i].to, w = e[i].val;//使用新加入的点更新其他点距离
			if (!in[v] and w < dis[v]) dis[v] = w;
		}
	}
	
	cout << ans << '\n';
	return 0;
}

Luogu P3366

　　

　　

时间复杂度 O (n^2)

使用堆优化可到 O ((N + M) log N)

不过，一般使用 Prim 算法都是完全图，M 和 N^2 同阶，复杂度甚至不如朴素 Prim，所以此处只给出朴素代码。

 

Boruvka

Boruvka 是每次找到各个连通块之间的最短边来求解最小生成树的算法。

它的优势在于一些不给定边，而给出两点之间连边权值计算方式的图，它的效率会比较高。

不过仍是十分冷门的算法。

 

算法过程

  • 所有点都属于不同的连通块
  • 遍历每个连通块，找到它与其他连通块的最短边
  • 合并每个连通块与最短边相连的另一个连通块
  • 重复 2, 3 步，直到所有点同属一个连通块，结束

 

证明

可以看出这个算法是 Kruskal 和 Prim 的缝合怪。

正确性是显然的。

连通块数量每次都会减半，所以时间复杂度也是可过的。

 

代码示例

#include <bits/stdc++.h>

using namespace std;
const int Maxn = 5e3 + 7, Maxm = 4e5 + 7;

struct Edge{ int nxt, to, val; }e[Maxm]; int head[Maxn], cnte;
int N, M, fa[Maxn], ans, mi[Maxn], cn[Maxn];

void add(int u, int v, int w) { e[++cnte] = (Edge){ head[u], v, w }; head[u] = cnte; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) fa[i] = i;
	for (int i = 1, u, v, w; i <= M; ++i)
		cin >> u >> v >> w, add(u, v, w), add(v, u, w);
	
	while (true) {
		memset(mi, 0x3f, sizeof(mi));
		for (int i = 1; i <= N; ++i)
			for (int j = head[i]; j ; j = e[j].nxt) { int u = find(i), v = find(e[j].to), w = e[j].val;
				if (u == v) continue;
				if (mi[u] > w) mi[u] = w, cn[u] = v;//找最短边和所连接的连通块
			}
		bool flag = true;
		for (int i = 1; i <= N; ++i) { int u = find(i), v = find(cn[u]);
			if (mi[i] != mi[0] and u != v) flag = false, ans += mi[i], fa[u] = v;//合并
		}
		if (flag == true) break;
	}
	
	for (int i = 1; i < N; ++i)
		if (find(i) != find(i + 1)) { cout << "orz" << '\n'; return 0; }
	
	cout << ans << '\n';
	return 0;
}

Luogu P3366

　　

时间复杂度 O((N + M) log N)

 

（严格）次小生成树

 定理

一棵（严格）次小生成树一定和一棵最小生成树有且只有一条边的差别。

由定理可知，我们可以通过先求出最小生成树，在加边删边以求（严格）次小生成树。

 

算法过程

  •  求最小生成树
  • 枚举每一条不在最小生成树上的边，加入它到集合中。
  • 这时会出现一个环，找出环上权值最大的边（不能是刚加入的边），删去它，用目前的边权和更新答案。
  • 重复此过程得到的最大值即为次小生成树。

 

具体实现

我们来看一个例子：

例子

求出最小生成树后，再加入权值为 k 的边 u->v 后，出现了一个环，而我们需要知道的是树上 u->v 的简单路径上，最大的边权（如果求严格次小生成树，要求这个数不能为 k）。

发现可以用树剖维护，如果求非严格次小生成树，可以用 ST，严格的话最好用线段树。

线段树部分，需要维护最大值和严格次大值，具体请看代码。

 

代码示例

 

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int Maxn = 1e5 + 7, Maxm = 3e5 + 7;

struct edge{ int fro, to, val; }t[Maxm];
struct Edge{ int nxt, to, val; }e[Maxm]; int head[Maxn], cnte;
int N, M, Fa[Maxn], sum, ans(1e18), block; bool vis[Maxm];
int siz[Maxn], dep[Maxn], fa[Maxn], top[Maxn], idx, dfn[Maxn], son[Maxn];
int mx[Maxn << 2], se[Maxn << 2], A[Maxn];

int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); }
void add(int u, int v, int w) { e[++cnte] = (Edge){ head[u], v, w }; head[u] = cnte; }
void dfs1(int u, int f) {
	siz[u] = 1, dep[u] = dep[fa[u] = f] + 1;
	for (int i = head[u]; i ; i = e[i].nxt) { int v = e[i].to;
		if (v == f) continue;
		dfs1(v, u); siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) son[u] = v;
	}
}
void dfs2(int u, int tp, int val) {
	top[u] = tp, dfn[u] = ++idx; A[idx] = val;
	if (!son[u]) return;
	for (int i = head[u]; i ; i = e[i].nxt)
		if (e[i].to == son[u]) { dfs2(e[i].to, tp, e[i].val); break; }
	for (int i = head[u]; i ; i = e[i].nxt) { int v = e[i].to, w = e[i].val;
		if (v == fa[u] or v == son[u]) continue;
		dfs2(v, v, w);
	}
}
#define ls p << 1
#define rs p << 1 | 1
void pushUp(int p) { mx[p] = max(mx[ls], mx[rs]); se[p] = max(mx[ls] == mx[rs] ? 0 : min(mx[ls], mx[rs]), max(se[ls], se[rs])); }
void build(int l, int r, int p) {
	if (l == r) { mx[p] = A[l]; return; } int mid = (l + r) >> 1;
	build(l, mid, ls), build(mid + 1, r, rs); pushUp(p);
}
int getmx(int l, int r, int s, int t, int k, int p) {
	if (r < s or t < l) return 0;
	if (l <= s and t <= r) return mx[p] == k ? se[p] : mx[p]; int mid = (s + t) >> 1;
	return max(getmx(l, r, s, mid, k, ls), getmx(l, r, mid + 1, t, k, rs));
}
int query(int x, int y, int k) {
	int res = 0;
	while (top[x] ^ top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		res = max(res, getmx(dfn[top[x]], dfn[x], 1, N, k, 1));
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	res = max(res, getmx(dfn[x] + 1, dfn[y], 1, N, k, 1));
	return res;
}

signed main() {
	ios::sync_with_stdio(false);
	cin >> N >> M; block = N;
	for (int i = 1; i <= N; ++i) Fa[i] = i;
	for (int i = 1; i <= M; ++i) {
		cin >> t[i].fro >> t[i].to >> t[i].val;
		if (t[i].fro == t[i].to) { --i, --M; }
	}
	
	sort(t + 1, t + 1 + M, [](const edge& x, const edge& y) { return x.val < y.val; });
	for (int i = 1; i <= M; ++i) { int u = find(t[i].fro), v = find(t[i].to);
		if (u == v) continue; --block; Fa[u] = v; sum += t[i].val; vis[i] = true;
		add(t[i].fro, t[i].to, t[i].val), add(t[i].to, t[i].fro, t[i].val);
		if (block == 1) break;
	}
	
	dfs1(1, 0), dfs2(1, 1, 0), build(1, N, 1);
	
	for (int i = 1; i <= M; ++i) {
		if (vis[i]) continue;
		int tot = query(t[i].fro, t[i].to, t[i].val);
		ans = min(ans, sum + t[i].val - tot);
	}
	cout << ans << '\n';
	return 0;
}

Luogu P4180

　　

关于生成树的全部常用知识已经介绍完毕，如有问题请私信作者 @qkhm

（注：本文所有内容仅针对算法竞赛，如有不严谨还请海涵）

标签：连通,val,int,笔记,生成,fa,算法,Maxn
From： https://www.cnblogs.com/qkhm/p/17740304.html

相关文章

  • 利用 Javascript 生成数字序列
    <!DOCTYPEhtml><html><head><title>生成数字序列</title></head><body><h1>Element对象之innerHTML属性</h1><pid="demo"onclick="myFunction()">点击生成数字序列</p><script>funct......
  • 国产开源无头CMS，MyCms v4.7 快捷生成接口开发后台
    MyCms是一款基于Laravel开发的开源免费的开源多语言商城CMS企业建站系统。MyCms基于Apache2.0开源协议发布，免费且可商业使用，欢迎持续关注我们。v4.7更新内容opt:公众号菜单优化dev:API接口生成管理dev:数据表CURD管理opt:后台返回列表按钮opt:插件兼容版本......
  • Python生成随机整数数组的实用方法
    在编程中，生成随机整数数组是一项非常常见的任务。本文将介绍如何使用Python语言来生成随机整数数组，帮助读者掌握这一有用的编程技巧。通过实际的代码示例，我们将逐步指导读者完成生成随机整数数组的过程，并提供一些实际应用的建议。第一部分：了解随机数生成原理1.什么是随机数：-随机数......
  • SWUST 算法分析与设计 实验报告2
    合并排序实验报告 一、     实验内容及目的实验内容：对合并排序算法进行算法描述、效率分析、实验结果分析。实验目的：深入理解分治法的思想，学习合并排序的排序方法，对合并排序进行算法分析，通过与其他排序算法比较，体会分治思想的优点。分析的指标：在相同数据规模的情况......
  • 学习笔记-设计模式-创建型模式-单例模式
    单例模式一个类只有一个实例，并提供一个全局访问此实例的点，哪怕多线程同时访问。单例模式主要解决了一个全局使用的类被频繁的创建和消费的问题。单例模式的案例场景数据库的连接池不会反复创建spring中一个单例模式bean的生成和使用在我们平常的代码中需要设置全局的一些属......
  • 【2023年09月28日】stf61-测试基础第一天笔记
    stf61-测试基础第一天笔记计算机基础计算机既可以做数值运算，也可以做逻辑运算。数值运算：加减乘除等针对数值的操作逻辑运算：运算结果是真或者假的这一类运算，多用于条件判断举例：a=10,b=20如果a>b并且a>0,那么就执行a+b的操作，否则执行a-b的操作。a>b并且a>0——》逻辑运算a+b,a-b——......
  • 华为云 海报生成 CDN权限配置
    在【对象存储服务】中，找到【CDN】选择进入  选择【域名管理】，添加绑定的【CDN域名】并解析好  选择【绑定的CDN域名】的【设置】中，找到【高级配置】    在【HTTPheader配置】边，点击【编辑】  添加【access-control-allow-origin】，取值为“*”的权限，即可......
  • 腾讯云COS海报生成配置教程
    系统对接了腾讯云COS，生成海报却没有加载图片，还需要做一下的配置哟~ 登录上腾讯云的控制台（https://console.cloud.tencent.com/） 找到【内容分发网络】，在【域名管理】处，点击【添加域名】的按钮    加速区域根据运营的需求进行选择；加速域名这边填写一个二级域名；《源......
  • Asp-Net-Core开发笔记：EFCore统一实体和属性命名风格
    前言C#编码规范中，类和属性都是大写驼峰命名风格（PascalCase/UpperCamelCase），而在数据库中我们往往使用小写蛇形命名（snake_case），在默认情况下，EFCore会把原始的类名和属性名直接映射到数据库，这不符合数据库的命名规范。为了符合命名规范，而且也为了看起来更舒服，需要自己做命名转换......
  • 【Pytorch】小土堆笔记（未完成）
    transforms在训练的过程中，神经网络模型接收的数据类型是Tensor，而不是PIL对象，因此我们还需要对数据进行预处理操作，比如图像格式的转换。同时我们可以对图片进行一系列图像变换与增强操作，例如裁切边框、调整图像比例和大小、标准化等，以便模型能够更好地学习到数据的特征。这些......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99