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

Kruskal 重构树学习笔记

时间：2024-01-22 22:48:09浏览次数：23  
标签：重构 int Kruskal 笔记 fa kruskal 权值 节点

1. 定义与构造

对于一张无向图，新建 \(n\) 个树，原图每个点在一个树中，权值是 \(0\)。按边权从小到大枚举边，如果这条边两个节点不在一棵树，合并两个节点所在的树。新建一个点，点权为加入边的边权，同时将两棵树的根节点分别设为新建点的左儿子和右儿子，将新建点设为根。

实现与 Kruskal 最小生成树算法类似，用并查集实现。

代码：

struct edge{
	int u, v, w;
	bool operator <(const edge &p) const
	{
		return w < p.w;
	}
}e[N];

int gfa(int i)
{
	return i == fa[i] ? i : (fa[i] = gfa(fa[i]));
}

void Kruskal()
{
	for(int i = 1; i < n * 2; i ++ ) fa[i] = i;
	k = n;
	sort(e + 1, e + m + 1);
	for(int i = 1; i <= m; i ++ )
	{
		int u = gfa(e[i].u), v = gfa(e[i].v);
		if(u != v)
		{
			w[ ++ k] = e[i].w;
			ls[k] = u, rs[k] = v;
			f[u] = f[v] = fa[u] = fa[v] = k;
		}
	}
}

2. 性质与应用

kruskal 重构树有以下性质：

  • 如果原图连通，重构树是一棵 \(2n-1\) 个节点的二叉树，根节点是最后插入的节点，每个编号小于等于 \(n\) 的节点没有儿子，编号大于 \(n\) 的节点有两个儿子。
  • 满足大根堆的性质，即每个节点权值大于等于儿子节点权值。
  • 原图中两个点之间的所有路径上最大边权的最小值等于 Kruskal 重构树上两点之间的 LCA 的权值。

由这些性质，kruskal 重构树主要有两种应用（可能不全，碰到再补充）：

  • 在线求一个无向图两点间简单路径的最大边权最小值。
  • 在线修改和查询所有可以由一个点 \(u\) 不通过权值大于 \(w\) 的点的信息：用树上倍增找到 \(u\) 父节点中满足权值小于等于 \(w\) 的深度最浅的节点 \(v\)，则满足条件的点是 \(v\) 的子树中所有叶子节点。

实际上对于第二个应用，如果不强制在线且没有修改操作，可以用并查集实现：边按权排序，询问按 \(w\) 排序，处理每个询问前用并查集连边权小于 \(w\) 的边，用并查集处理询问，时间复杂度 \(O(nlogn)\)

3. 题目

(1) P3684 [CERC2016]机棚障碍 Hangar Hurdles

链接

首先用二分法求出每个点为中心的正方形最大边长，然后所有相邻的点连一条边权值为两个点最大边长的最小值，问题转化为在无向图上求两个点路径最小边权最大值，构建 kruskal 重构树求 LCA 即可。时间复杂度 \(O(n^2logn)\)

代码

// 求最大正方形边长

int get(int ax, int ay, int bx, int by)
{
	return s[bx][by] - s[ax - 1][by] - s[bx][ay - 1] + s[ax - 1][ay - 1];
}

for(int i = 1; i <= n; i ++ )
	for(int j = 1; j <= n; j ++ )
		s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] == '#');
	
for(int i = 1; i <= n; i ++ )
	for(int j = 1; j <= n; j ++ )
	{
		int l = 0, r = min(min(i, n - i + 1), min(j, n - j + 1)), mid;
		while(l < r)
		{
			mid = l + r + 1 >> 1;
			if(get(i - mid + 1, j - mid + 1, i + mid - 1, j + mid - 1)) r = mid - 1;
			else l = mid;
		}
		t[i][j] = l;
	}

// Kruskal 重构树

void kruscal()
{
	k = n * n;
	for(int i = 1; i < k * 2; i ++ ) fa[i] = i;
	sort(e + 1, e + m + 1);
	for(int i = 1; i <= m; i ++ )
	{
		int u = gfa(e[i].u), v = gfa(e[i].v);
		if(u != v)
		{
			w[ ++ k] = e[i].w;
			ls[k] = u, rs[k] = v;
			f[u][0] = f[v][0] = fa[u] = fa[v] = k;
		}
	}
}

void dfs(int u)
{
	dep[u] = dep[f[u][0]] + 1;
	for(int i = 1; i < K; i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];
	if(ls[u]) dfs(ls[u]), dfs(rs[u]);
}

int lca(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = K - 1; i >= 0; i -- )
		if(dep[f[u][i]] >= dep[v])
			u = f[u][i];
	if(u == v) return u;
	for(int i = K - 1; i >= 0; i -- )
		if(f[u][i] != f[v][i])
			u = f[u][i], v = f[v][i];
	return f[u][0];
}

// 调用

w[lca(u, v)];

(2) 万松园

题意描述：给定一棵 \(n\) 个节点的树，多次询问，每次询问给定 \(u,w\)，求 \(u\) 不经过边权小于 \(w\) 的边能到达点的数量。

第二个运用。记录重构树上每个 \(2^k\) 级祖先，查询时从大到小枚举 \(k\)，如果 \(u\) 的 \(2^k\) 级祖先的权值大于等于 \(w\)，\(u\) 设为 \(u\) 的 \(2^k\) 级祖先。

因为不强制在线，用并查集可以做而且思路比较简单。

可以发现，无论是并查集的离线做法还是 Kruskal 重构树的在线做法，重构树的在线做法，原图是树的条件没有多大作用，只是合并的时候可以不用判断是否在一个集合，也就是说，一般的无向图也可以用这种做法。所以，这个条件是用来钓鱼的

代码

int gfa(int i)
{
	return i == fa[i] ? i : (fa[i] = gfa(fa[i]));
}

void kruskal()
{
	sort(e + 1, e + m + 1);
	for(int i = 1; i < n * 2; i ++ ) fa[i] = i;
	k = n;
	for(int i = 1; i <= m; i ++ )
	{
		int u = gfa(e[i].u), v = gfa(e[i].v);
		w[ ++ k] = e[i].w;
		ls[k] = u, rs[k] = v;
		f[u][0] = f[v][0] = fa[u] = fa[v] = k;
	}
	w[0] = -1;
}

void dfs(int u)
{
	for(int i = 1; i < K; i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];
	if(ls[u])
	{
		dfs(ls[u]), dfs(rs[u]);
		cnt[u] = cnt[ls[u]] + cnt[rs[u]];
	}
	else cnt[u] = 1;
}

int query(int u, int k)
{
	for(int i = K - 1; i >= 0; i -- )
		if(w[f[u][i]] >= k)
			u = f[u][i];
	return cnt[u] - 1;
}

(3) P4768 [NOI2018] 归程

链接

首先可以想到求所有点到终点的最短路径，即节点 1 到所有点的最短路径，用Dijkstra 算法求（SPFA 就在这里死的）。

问题转换为给定 \(u,w\)，求 \(u\) 不经过边权小于等于 \(w\) 的边能到达点的到 1 节点的距离的最小值，构造 kruskal 重构树用书上倍增解。

代码

void dijkstra()
{
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	memset(mark, 0, sizeof mark);
	priority_queue<PII, vector<PII>, greater<PII> > pq;
	pq.push({0, 1});
	
	while(pq.size())
	{
		int u = pq.top().y;
		pq.pop();
		if(mark[u]) continue;
		mark[u] = true;
		
		for(int i = h[u]; i; i = ne[i])
		{
			int v = en[i];
			if(dis[v] > dis[u] + le[i])
			{
				dis[v] = dis[u] + le[i];
				pq.push({dis[v], v});
			}
		}
	}
}

int gfa(int i)
{
	return i == fa[i] ? i : (fa[i] = gfa(fa[i]));
}

void kruskal()
{
	for(int i = 1; i < n * 2; i ++ ) fa[i] = i;
	k = n;
	sort(e + 1, e + m + 1);
	for(int i = 1; i <= m; i ++ )
	{
		int u = gfa(e[i].u), v = gfa(e[i].v);
		if(u != v)
		{
			w[ ++ k] = e[i].w;
			ls[k] = u, rs[k] = v;
			f[u][0] = f[v][0] = fa[u] = fa[v] = k;
		}
	}
	w[0] = -INF;
}

void dfs(int u)
{
	for(int i = 1; i < K; i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];
	mindis[u] = dis[u];
	if(ls[u]) dfs(ls[u]), mindis[u] = min(mindis[u], mindis[ls[u]]);
	if(rs[u]) dfs(rs[u]), mindis[u] = min(mindis[u], mindis[rs[u]]);
}

int query(int u, int t)
{
	for(int i = K - 1; i >= 0; i -- )
		if(w[f[u][i]] > t)
			u = f[u][i];
	return mindis[u];
}

(4) Donation

链接

一道在 kruskal 重构树上 DP 的题。

首先，捐钱比较难想，可以反过来思考倒着走领钱的思路。

显然，在第一次经过一个节点的时候领钱是最优的，对于节点 \(i\)，令 \(c_i=\max\{a_i-b_i,0\}\)，若当前的钱数是 \(v\)，到节点 \(i\) 的条件是 \(v\ge c_i\)，如果不满足则把 \(v\) 补充到 \(c_i\)，同时如果是第一次经过，\(v\) 就变成 \(v+b_i\)。

对于边 \((u_i,v_i)\)，令边权等于 \(\max\{c_{u_i},c_{v_i}\}\) 表示经过这条边当前钱数的最小值，按边权从小到大排序建 kruskal 重构树。

考虑在这棵树上 dp。设 \(f_u\) 表示经过所有 \(u\) 的子树节点（不一定回到 \(u\)）后最小的领到的钱。对于叶子节点，\(f_u=b_u+c_u\)；对于非叶子节点，枚举是从哪个子节点来的 \(u\)，由于 kruskal 重构树的权值上大下小，只需要考虑这子树到 \(u\) 的部分，另一棵子树直接领钱，所有方程为 \(f_u=\min\{max(f_x,c_u)+s_u-s_x,max(f_y,c_u)+s_u-s_y\}\)，其中 \(x,y\) 分别是 \(u\) 的两个儿子，\(s_u\) 表示 \(u\) 为根的子树内节点 \(b\) 值之和。

#include <bits/stdc++.h> 

using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

int n, k, m, a[N], b[N];
struct edge{
	int u, v, w;
	bool operator <(const edge &p) const
	{
		return w < p.w;
	}
}e[N];
int pe[N];
int fa[N], ls[N], rs[N];
LL f[N], s[N];

int gfa(int i)
{
	return i == pe[i] ? i : (pe[i] = gfa(pe[i]));
}

void kruskal()
{
	for(int i = 1; i < n * 2; i ++ ) pe[i] = i;
	k = n;
	sort(e + 1, e + m + 1);
	for(int i = 1; i <= m; i ++ )
	{
		int u = gfa(e[i].u), v = gfa(e[i].v);
		if(u != v)
		{
			fa[u] = fa[v] = pe[u] = pe[v] = ++ k;
			ls[k] = u, rs[k] = v;
			a[k] = e[i].w;
		}
	}
}

void dp()
{
	for(int u = 1; u <= n; u ++ )
	{
		f[u] = a[u] + b[u];
		s[u] = b[u];
	}
	for(int u = n + 1; u <= k; u ++ )
	{
		s[u] = s[ls[u]] + s[rs[u]];
		f[u] = min(max(f[ls[u]], (LL)a[u]) + s[u] - s[ls[u]], max(f[rs[u]], (LL)a[u]) + s[u] - s[rs[u]]);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++ )
	{
		scanf("%d%d", &a[i], &b[i]);
		a[i] = max(a[i] - b[i], 0);
	}
	for(int i = 1; i <= m; i ++ )
	{
		scanf("%d%d", &e[i].u, &e[i].v);
		e[i].w = max(a[e[i].u], a[e[i].v]);
	}
	kruskal();
	dp();
	printf("%lld\n", f[k]);
	return 0;
}

小结

最大边最小=最小 \(x\) 保留大于等于 \(x\) 的边连通=最小生成树。

两两之间最小瓶颈最大值=重构树按 DFS 序排序后相邻两点 LCA 权值最大值。

计算一条边的贡献。

找权值满足要求深度最小的点，除了倍增以外，还可以树剖+二分。

标签：重构,int,Kruskal,笔记,fa,kruskal,权值,节点
From： https://www.cnblogs.com/recollect-the-past/p/17981253

相关文章

  • Docker 学习笔记 - 5
    DockerFile解析是什么Dockerfile是用来构建Docker镜像的构建文件，由一系列命令和参数构成的脚本构建三步骤编写Dockerfile文件dockerbuilddockerrun文件什么样？？？熟悉的Centos为例http://hub.docker.com/_/centosDockerFile构建过程解析Dockerfile内容基础知识1、每条......
  • C++学习笔记
    C++学习笔记（1）预编译、编译、链接预编译(Preprocessing)cppreference中：GPT这么说：C++预编译是指在编译阶段之前对代码进行的一系列预处理操作。预编译的目的是为了将代码中的预处理指令和宏展开，以及进行一些其他的预处理操作。预处理指令包括以井号（#）开头的指令，如#include、#......
  • Inplementation of Binary Search Tree【1月22日学习笔记】
    点击查看代码//InplementationofBinarySearchTree#include<iostream>usingnamespacestd;structbstnode{ intdata; bstnode*left; bstnode*right;};/*bstnode*root=NULL;*//*root=NULL;wrong*//*全局范围内的变量的初始化必须在声......
  • 学习笔记438—《赤兔之死》高考满分文章
    建安二十六年，公元221年，关羽走麦城，兵败遭擒，拒降，为孙权所害。其坐骑赤兔马为孙权赐予马忠。一日，马忠上表：赤兔马绝食数日，不久将亡。孙权大惊，急访江东名士伯喜。此人乃伯乐之后，人言其精通马语。马忠引伯喜回府，至槽间，但见赤兔马伏于地，哀嘶不止。众人不解，惟伯喜知之。伯喜遣散诸人，抚其......
  • 数据库学习笔记（四）—— MySQL 之 事务篇
    MySQL之事务篇事务事务是访问并可能操作各种数据项的一个数据库操作序列，这些操作要么全部执行,要么全部不执行，是一个不可分割的工作单位。事务由事务开始与事务结束之间执行的全部数据库操作组成。事务的四大特性（ACID）：A原子性：原子性是指包含事务的操作要么全部执行......
  • 数据库学习笔记（三）—— MySQL 之 SELECT（查询）篇
    查询单表查询select分组函数，分组后的字段from表名[where条件][groupby分组的字段][having分组后的筛选][orderby排序列表];排序SELECT字段名FROM表名ORDERBY字段名[ASC|DESC];ASC表示升序，DESC表示降序，而ORDERBY默认值为ASC。多字段排......
  • openGauss学习笔记-204 openGauss 数据库运维-常见故障定位案例-重建索引失败
    openGauss学习笔记-204openGauss数据库运维-常见故障定位案例-重建索引失败204.1重建索引失败204.1.1问题现象当Desc表的索引出现损坏时，无法进行一系列操作，可能的报错信息如下。index\"%s\"containscorruptedpageatblock%u",RelationGetRelationName(rel),BufferG......
  • 0122今日笔记
    一java环境搭建jdk长期支持版本jdk8111721可以到oracle官网下载自己需要的jdk版本下载后安装到D盘(建议不要在c盘)在电脑系统中找到系统设置找到系统环境在系统变量中创建JAVAHOME路径就是直接的dk路径然后在pa然后一直点击确定就行测试是否成功按win+R+cmd进......
  • python学习笔记10（循环结构2）
    一）循环结构21、扩展模式语法：for循环变量in遍历对象：语句块1else:语句块2说明：else在循环结束后执行，通常和break和continue结合使用2、无限循环whilewhile表达式：语句块例子：answer=input('今天要上课么？y/n')whileanswer=='y':print('好好学习，天天向上')answer=input('今......
  • 笔记本也能飞：运行chat大模型
    背景在过去的一年，ChatGPT的崛起彻底改变了我们与AI的交互方式。它不再是被动的信息提供者，而是成为了一个可以与我们自由交流、分享知识的伙伴。无论是生活中的琐事，还是工作中的难题，ChatGPT都能给出有价值的建议和信息。同时，ChatGPT也在各个领域引发了深远的变革。在教育领域，Chat......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99