Kruskal重构树

突然写起了归程，就先来复习一下

Kruskal重构树

性质

是一个小/大根堆(由建树时边权的排序方式决定)

建树

重构树中把原树的点权转换成为了新建节点的边权

先将边权排序
依次遍历每条边，若改变连接的两个节点u和v 不在一个并查集内，就新建一个结点node，该点点权为这条边的边权，找到 $u,v$ 所在并查集的根 $u_i,v_i$，连边$(node,u_i)(node,v_i)$，并更新并查集 $fa[u_i]=node,fa[v_i]=node$

void kruskal()
{
    int tot=n;
	for(int i=1;i<=n;++i) f1[i]=i;
	sork(a+1,a+1+m,cmp);
	for(int i=1;i=m;++i)
	{
		int u=find(a[i].u),v=find(a[i].v);
		if(u!=v)
		{
			w[++tot]=e[i].w;
			f1[tot]=f1[u]=f1[v]=tot;
			add(u,cnt),add(cnt,u);
			add(v,cnt),add(cnt,v);
		}
	}
}

建树复杂度：复杂度：$O(nlogn)$

例题

接下来我们来看一个简单的例题

BZOJ3732 Network

给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： $d_j ( 1 < = d_j < = 1,000,000,000)$

现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

对于这个题目，我们很容易想到用树剖维护，或者说直接最小生成树+LCA进行维护，这一类的题目在NOIP模拟的时候就写了很多，最小生成树+LCA。
这里，我们使用Kruskal重构树来解决这个问题

Kruskal重构树若我们开始时将边权升序排序
则LCA(u,v)的权值代表原图 u到v路径上最大边权的最小值
由于边权越大的结点深度越小
所以在这棵树上u到v的路径显然就是原图上u到v尽量沿着边权小的边走
而LCA(u,v)显然就是u到v路径上深度最小的结点
反之若我们一开始将边权降序排序
则LCA(u,v)的权值代表原图 u到v路径上最小边权的最大值

#include
#include
#include
#include
using namespace std;

#define ll long long
#define re register
#define gc getchar()
inline int read()
{
 	re ll x(0),f(1);re char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
} 

const int N=2e5+10;
int n,m,q,cnt,h[N],f1[N],w[N],tot;
struct edge {int u,v,w;}a[N];
struct node {int next,to;}e[N];
bool cmp(edge a,edge b){return a.wsiz[son[u]])
				son[u]=v;
		}
}
void dfs2(int u)
{
	if(son[u])
		top[son[u]]=top[u],dfs2(son[u]);
	QXX(u)
		if(v!=fa[u]&&v!=son[u])
			top[v]=v,dfs2(v);
}

void kruskal()
{
    tot=n;
	for(int i=1;i<=n;++i) f1[i]=i;
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;++i)
	{
		int u=find(a[i].u),v=find(a[i].v);
		if(u!=v)
		{
			w[++tot]=a[i].w;
			f1[tot]=f1[u]=f1[v]=tot;
			add(u,tot),add(tot,u);
			add(v,tot),add(tot,v);
		}
	}
}

int lca(int u,int v)
{
	while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
        else v=fa[top[v]];
    }
    if(dep[u]

Kruskal重构树

Kruskal重构树

性质

建树

例题

相关

标签