首页 > 其他分享 >Kruskal 重构树学习笔记

Kruskal 重构树学习笔记

时间：2023-10-08 21:57:25浏览次数：37  
标签：重构 typedef tot int Kruskal long le edge 笔记

模拟赛突然出了这个，，，被创死了

定义

我们先回顾最基本的 Kruskal 算法。

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

那什么事 Kruskal 重构树呢？

就是用类似Kruskal的方法来把一个图重构成一颗树。

实现方法

按照最小生成树的方法先把边权从小到大排序，然后一次考虑每条边。

如果这条边连接的两个端点已经连通就跳过，还没连通就建一个新点，把这个新点的权值设为这条边的权值，让这个新点向两个端点的根节点连边。

具体实现方法如下：

tot = n;
dsu.init();
for(int i = 1; i <= m; i ++)
	cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
sort(edge + 1, edge + 1 + m);
for(int i = 1; i <= m; i ++) {
	int u = dsu.find(edge[i][1]), v = dsu.find(edge[i][2]);
	if(u == v) continue;
	tot ++;
	dsu.fa[u] = dsu.fa[v] = tot;
	e[tot].push_back(u);
	e[tot].push_back(v);
	val[tot] = edge[i][0];
}

优秀性质：

  • 是一棵二叉树。

  • 如果是按最小生成树建立的话是一个大根堆。

  • 原图中两个点间所有路径上的边最大权值的最小值 \(=\) 最小生成树上两点简单路径的边最大权值 \(= \text{Kruskal}\) 重构树上两点 \(\text{LCA}\) 的点权。

例题

1. P2245 星际导航

显然是板子题，直接利用性质 3，会写 LCA 就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, M = 3e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, q;
array<int, 3> edge[M];
int p[N];
int fa[N][20], val[N], dep[N];
vector<int> e[N];
int tot;
int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]);
}
void dfs(int u, int fath) {
	dep[u] = dep[fath] + 1;
	fa[u][0] =  fath;
	for(int i = 1; i <= __lg(dep[u]); i ++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : e[u]) dfs(v, u); 
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	while(dep[u] != dep[v]) u = fa[u][__lg(dep[u] - dep[v])];
	if(u == v) return u;
	for(int k = __lg(dep[u]); ~k; k --)
		if(fa[u][k] != fa[v][k]) 
			u = fa[u][k], v = fa[v][k];
	return fa[u][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= n * 2; i ++) p[i] = i;
	for(int i = 1; i <= m; i ++)
		cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	tot = n;
	sort(edge + 1, edge + 1 + m);
	for(int i = 1; i <= m; i ++) {
		int u = find(edge[i][1]), v = find(edge[i][2]);
		if(u == v) continue;
		tot ++;
		p[u] = p[v] = tot;
		e[tot].push_back(u);
		e[tot].push_back(v);
		val[tot] = edge[i][0];
	}
	for(int i = 1; i <= tot; i ++)
		if(find(i) == i) dfs(i, 0);
	cin >> q;
	while(q --) {
		int u, v;
		cin >> u >> v;
		if(find(u) != find(v)) cout << "impossible\n";
		else cout << val[lca(u, v)] << '\n';
	}
    return 0;
}

2.囹圄

同学出的题，就不放链接了。

题意：

在一个神奇的国家有 \(n\) 个地点，以及 \(m\) 条道路连接这些地点，每个地点有一个局限值 \(a_i\)。

同时，定义一个地点的广阔度为其能到达的地方的局限值中没有出现过的最小正整数。

最近这个国家打算修路，有 \(q\) 次操作，分为修路和询问

1 x y 表示修一条连接 \(x\) 和 \(y\) 的路。

2 x 表示查询 \(x\) 的广阔度。

对于 \(100%\) 的数据 \(1\le n,m\le 3\times 10^5\) ，\(1\le q\le 1\times 10^6\) ，\(1\le a_i \le n\)。

分析：

有一个显然的 \(O(n \log ^ 2 n)\) 的并查集启发式合并，暴力维护 mex 的做法，可以通过，但是不是最优解这里只提一嘴。

最优解显然可以线段树合并，但是我没学。

考虑按询问顺序建重构树，对于每次询问，倍增寻找能到的节点，把叶子节点建立权值线段树。

然后就可以 P4137了。

3. 黄队

模拟赛题，链接放了也没人进得去（

有一棵 \(n\) 个节点的树，其中所有的树边 \(1\) 到 \(n−1\) 标号。定义 \(δ(v,r)\) 为 \(v\) 经过由标号不超过 \(r\) 的边构成的路径到达的点集。

现在有 \(q\) 个询问，每个询问给你一组点 \(v_1,v_2,…,v_k\)，求 \((r_1,r_2,…,r_k)\) 这样的 k 元组个数，满足 $ 0 \le r_i \le n - 1 $ 且\(δ(v_i,r_i)\) 这些点集两两不交。

由于答案很大，请输出对 \(10^9+7\) 取模的值。

对于 \(100%\) 的数据，满足 \(n, q,\sum k \le 10^5\) 。

分析：

杜老师几年前出的题，性质还是很好找的，找到性质就 80 pts 了（

考虑 \(u, v\) 两点，如果他们之间的路径上最大边权是 \(w\)，那么有 \(r_u,r_v < w\)，否则 \(u\) 或者 \(v\) 的球就会包含另
1 个点。

所以 \(r_u\) 要小于到其他所有点的路径最大边权的最小值。

到这里之后暴力就有 80 了，就是我场上拿的分。（

考虑建出重构树，每次询问按 \(dfn_u\) 排序，每个点的最小值一定是跟他相邻的点的 LCA 取到，所以排完序后每个点就只要算两边的了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 4e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, q, tot;
int p[N], val[N], fa[N][20], dep[N], dfn[N], tim;
int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]);
}
vector<int> e[N];
void dfs(int u, int fath) {
	fa[u][0] = fath;
	dfn[u] = ++ tim;
	dep[u] = dep[fath] + 1;
	for(int i = 1; i <= __lg(dep[u]); i ++) 
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : e[u]) dfs(v, u);
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	while(dep[u] != dep[v]) u = fa[u][__lg(dep[u] - dep[v])];
	if(u == v) return u;
	for(int k = __lg(dep[u]); ~k; k --) 
		if(fa[u][k] != fa[v][k]) 
			u = fa[u][k], v = fa[v][k];
	return fa[u][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	tot = n;
	for(int i = 1; i <= n * 2; i ++) p[i] = i;
	for(int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		u = find(u), v = find(v);
		tot ++;
		p[u] = p[v] = tot;
		e[tot].push_back(u);
		e[tot].push_back(v);
		val[tot] = i;
	}
	cin >> q;
	dfs(tot, 0);
	while(q --) {
		int k;
		int ans = 1;
		cin >> k;
		vector<int> a(k);
		for(int i = 0; i < k; i ++)
			cin >> a[i];
		sort(a.begin(), a.end(), [](int x, int y) {
			return dfn[x] < dfn[y];
		});
		for(int i = 0; i < k; i ++) {
			int tmp = n - 1;
			if(i) tmp = val[lca(a[i], a[i - 1])] - 1;
			if(i < k - 1) tmp = min(tmp, val[lca(a[i], a[i + 1])] - 1);
			ans = (LL)(tmp + 1ll) * ans % mod;
		}
		cout << ans << '\n';
	}
    return 0;
}

4.P7834 [ONTAK2010] Peaks 加强版

求从 \(u\) 开始只经过权值 \(\leq x\) 的边所能到达的点，这个可以重构树上倍增求解，求出左右端点，就变成区间第 \(k\) 大了，直接主席树即可。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, M = 5e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, q;
int h[N];
vector<int> hs;
array<int, 3> edge[M];
vector<int> e[N];
int val[N], fa[N][25], p[N], L[N], R[N], dep[N];
struct DSU {
	int fa[N];
	void init() {
		for(int i = 1; i <= n * 2; i ++) fa[i] = i;
	}
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);	
	}
} dsu;
int tot, idx;
void dfs(int u, int fath) {
	L[u] = idx;
	if(u <= n) p[++ idx] = u;
	dep[u] = dep[fath] + 1;
	fa[u][0] = fath;
	for(int i = 1; i <= __lg(dep[u]); i ++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : e[u]) dfs(v, u);
	R[u] = idx;
}
struct SegT {
	int l, r, val;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define val(x) tr[x].val
} tr[N << 5];
int rt[N], cnt;
void pushup(int x) {
	val(x) = val(l(x)) + val(r(x));
}
void build(int &x, int l, int r) {
	x = ++ cnt;
	if(l == r) return;
	int mid = l + r >> 1;
	build(l(x), l, mid), build(r(x), mid + 1, r);
}
void insert(int &x, int lst, int pos, int l, int r) {
	x = ++ cnt;
	tr[x] = tr[lst];
	if(l == r) {
		val(x) ++;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) insert(l(x), l(lst), pos, l, mid);
	else insert(r(x), r(lst), pos, mid + 1, r);
	pushup(x);
}
int query(int x, int y, int l, int r, int k) {
	if(l == r) return l;
	int cnt = val(r(y)) - val(r(x)), mid = l + r >> 1;
	if(k <= cnt) return query(r(x), r(y), mid + 1, r, k);
	else return query(l(x), l(y), l, mid, k - cnt);
}
int get(int u, int x) {
	for(int i = 19; ~i; i --)
		if(val[fa[u][i]] <= x) u = fa[u][i];
	return u;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i ++) {
		cin >> h[i];
		hs.push_back(h[i]);
	}
	sort(hs.begin(), hs.end());
	hs.erase(unique(hs.begin(), hs.end()), hs.end());
	for(int i = 1; i <= n; i ++) {
		h[i] = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin() + 1;
	}
	tot = n;
	dsu.init();
	for(int i = 1; i <= m; i ++)
		cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	sort(edge + 1, edge + 1 + m);
	for(int i = 1; i <= m; i ++) {
		int u = dsu.find(edge[i][1]), v = dsu.find(edge[i][2]);
		if(u == v) continue;
		tot ++;
		dsu.fa[u] = dsu.fa[v] = tot;
		e[tot].push_back(u);
		e[tot].push_back(v);
		val[tot] = edge[i][0];
	}
	val[0] = LLONG_MAX;
	for(int i = tot; i >= 1; i --)
		if(dsu.fa[i] == i) dfs(i, 0);
	build(rt[0], 1, hs.size());
	for(int i = 1; i <= n; i ++) {
		insert(rt[i], rt[i - 1], h[p[i]], 1, hs.size());
	}
	int lst = 0;
	while(q --) {
		int v, x, k;
		cin >> v >> x >> k;
		v = (v ^ lst) % n + 1;
		k = (k ^ lst) % n + 1;
		x ^= lst;
		v = get(v, x);
		if(R[v] - L[v] < k) cout << -1 << '\n', lst = 0;
		else {
			lst = hs[query(rt[L[v]], rt[R[v]], 1, hs.size(), k) - 1];
			cout << lst << '\n';
		}
	}
    return 0;
}

标签：重构,typedef,tot,int,Kruskal,long,le,edge,笔记
From： https://www.cnblogs.com/Svemit/p/17750253.html

相关文章

  • 模糊测试原理（学习笔记）
    目录0x01什么是模糊测试0x02基本原理和组成1.基本原理基本思想基本概念2.系统组成值得一提：有关状态监控模块的处理0x03基础方法技术数据生成方法1.基本类型数据生成方法2.复合类型数据生成方法3.多阶段交互类型数据生成方法环境控制技术1.运行环境控制技术2.程序运行控制技术3.......
  • 《代码大全》阅读笔记04
    关键的“构建”决策，阅读了第四章之后，收获很多，具体内容如下：在真正构建之前，需要进行一些决策，首先是要选择语言，这貌似是一个难题，而且很有争议，其实对于具体程序员来说却不是一个问题，你几乎没啥选择权，老板让你用啥你就用啥吧，对新手来说，你会什么就找什么样的工作就是了，对于老手来说，公司......
  • Manacher学习笔记
    1.介绍:manacher算法用于求解回文子串问题，可以求出以一个串中每一点为中心的最长回文半径，相当于可以求出所有回文子串2.引入：假如要求出一个串所有长度为奇数的回文子串，暴力怎么做？枚举以每个点为回文中心，向两侧扩展，分别比较a[p+i]与a[p-i]时间复杂度O(n^2)我们考虑优化，我们......
  • Redis笔记
    redis数据类型字符串（String）:存储单个值。用例：存储文本、数字、计数器等。SETusername"john_doe"GETusername列表（List）：有序集合，允许重复元素。用例：消息队列、新闻推送、日志记录等。LPUSHtasks"task1"LPUSHtasks"task2"LRANGEtasks0-1LREM：LREM命令用于从......
  • iaas运维笔记记录
    iaas运维笔记记录镜像创建source/etc/keystone/admin-openrc.sh(挂载用户配置文件)glanceimage-create--name"cirros"--disk-formatqcow2--container-formatbare<cirros-0.5.2-x86_64-disk.qcow2--name:创建后的镜像名称--disk-format:镜像格式--contrainer-form......
  • 学习笔记421—Win7下使用U盘安装linux Ubuntu16.04双系统图文教程
    Win7下使用U盘安装linuxUbuntu16.04双系统图文教程安装步骤：1、下载Ubuntu16.04镜像软件；2、使用ultraISO软件制作U盘启动盘；3、利用U盘启动盘来安装Ubuntu系统；4、使用EasyBCD创建启动系统启动引导；5、重启系统即可。Ubuntu（友帮拓、优般图、乌班图）是一个以桌面应用为主的开源G......
  • 研发三维GIS系统笔记/框架改造/智能指针重构框架-003
    1.使用智能指针重构系统原有的系统都是裸指针，在跨模块与多线程中使用裸指针管理起来很麻烦，尤其是多任务系统中会出现野指针1classCELLTileTask:publicCELLTask2{3public:4CELLQuadTree*_node;5TileId_tileId;6CELL......
  • 学习笔记420—【译】理解LSTM（通俗易懂版）
    【译】理解LSTM（通俗易懂版）循环神经网络（RecurrentNeuralNetworks）人对一个问题的思考不会完全从头开始。比如你在阅读本片文章的时，你会根据之前理解过的信息来理解下面看到的文字。在理解当前文字的时候，你并不会忘记之前看过的文字，从头思考当前文字的含义。传统的神经网络并......
  • 密码协议学习笔记(8.16):几种特殊的秘密分享体系
    已知两个秘密的碎片,计算秘密的乘积的碎片:已知两个秘密$\alpha_0,\beta_0$分别实现了门限值为$t$的分享记$$f_{\alpha}(x)=\alpha_0+\alpha_1x+\cdots+\alpha_{t-1}x^{t-1}$$$$f_{\beta}(x)=\beta_0+\beta_1x+\cdots+\beta_{t-1}x^{t-1}$$秘密碎片为$$A_1=f_{\alpha}(1),A_2=......
  • Dapr学习笔记（二）-安装Dapr环境(Docker)
    安装DaprCLI。它使你能够启动、运行并管理Dapr实例。它还提供调试支持。安装 DockerDesktop。如果在Windows上运行，请确保将用于Windows的DockerDesktop配置为使用Linux容器。 备注默认情况下，Dapr使用Docker容器来为你提供最佳的全新体验。若要在D......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99