kruskal重构树学习笔记

一. SpringCloud简介与微服务架构

内容

按照 \(kruskal\) 算法的流程,把最小/大生成树中边权的关系映射到了一颗二叉树上

具体实现也很简单

在原本的 \(kruskal\) 算法中,每次查到两个不在同一集合的点,就新开一个节点

然后把两个节点的祖先节点分别向新节点连边,不计边权,但是要记录新点的点权,就是连接两个点的边的边权

新生成的树有以下特点

\(1\)、这棵树是一棵二叉树,且具有堆的性质。

\(2\)、树上除了叶子节点是原来的点,其余的点都是新建的点,且都有权值。

\(3\)、两个点 \(u\)\(v\)\(lca\) 的点权就对应着它们最小生成树上的路径上的最小/大值(瓶颈)

这样,我们就可以解决从某一个点出发,只能经过边权小于/大于 \(x\) 的边,在所有能到达的点中查询最值的问题

因为每遇到一个生成树上的边我们就会新开一个节点,所以节点数变为了原图的 \(2\)

P4768 [NOI2018] 归程

题目传送门

分析

可以说是 \(kruskal\) 重构树的板子题

回字有四种写法,那你知道单例有五种写法吗

首先按照边权从大到小排序,构建 \(kruskal\) 重构树

这样,重构树就是一个小根堆

因为每次询问时海拔大于 \(a\) 的边都可以乘车通过

所以我们肯定要在 \(v\) 能乘车到达的点中选择到 \(1\) 的最短路最短的点

在重构树上,我们只需要维护一个倍增数组

查询时倍增跳到第一个深度小于等于 \(a\) 的祖先节点

这个节点的子树中的所有点一定可以由 \(x\) 乘车到达

只要在这棵子树中查询到 \(1\) 的最短路的最小值就行了

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e6+5;
int h[maxn],tot=1,n,m,q,k,s,t,dis[maxn],cnt,fa[maxn],val[maxn];
struct Node{
	int zb,yb,val;
	Node(){}
	Node(rg int aa,rg int bb,rg int cc){
		zb=aa,yb=bb,val=cc;
	}
}jl[maxn];
bool cmp(rg Node aa,rg Node bb){
	return aa.val>bb.val;
}
int zhao(rg int xx){
	if(xx==fa[xx]) return xx;
	return fa[xx]=zhao(fa[xx]);
}
struct asd{
	int to,nxt,val;
}b[maxn];
void ad(rg int aa,rg int bb,rg int cc){
	b[tot].to=bb;
	b[tot].nxt=h[aa];
	b[tot].val=cc;
	h[aa]=tot++;
}
bool vis[maxn];
struct jie{
	int num,jl;
	jie(){}
	jie(rg int aa,rg int bb){
		num=aa,jl=bb;
	}
	bool operator <(const jie& A)const{
		return jl>A.jl;
	}
};
void dij(){
	std::priority_queue<jie> Q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	Q.push(jie(1,0));
	while(!Q.empty()){
		rg int now=Q.top().num;
		Q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(rg int i=h[now];i!=-1;i=b[i].nxt){
			rg int u=b[i].to;
			if(dis[u]>dis[now]+b[i].val){
				dis[u]=dis[now]+b[i].val;
				Q.push(jie(u,dis[u]));
			}
		}
	}
}
int dep[maxn],mindis[maxn],zx[maxn][22],mmin[maxn][22];
std::vector<int> g[maxn];
void dfs(rg int now,rg int lat){
	dep[now]=dep[lat]+1;
	mindis[now]=dis[now];
	mmin[now][0]=val[lat];
	zx[now][0]=lat;
	for(rg int i=1;(1<<i)<=dep[now];i++){
		zx[now][i]=zx[zx[now][i-1]][i-1];
		mmin[now][i]=std::min(mmin[now][i-1],mmin[zx[now][i-1]][i-1]);
	}
	for(rg int i=0;i<g[now].size();i++){
		rg int u=g[now][i];
		dfs(u,now);
		mindis[now]=std::min(mindis[now],mindis[u]);
	}
}
int latans;
int solve(rg int now,rg int val){
	for(rg int i=20;i>=0;i--){
		if(mmin[now][i]>val){
			now=zx[now][i];
		}
	}
	return mindis[now];
}
int main(){
	t=read();
	while(t--){
		memset(dep,0,sizeof(dep));
		memset(h,-1,sizeof(h));
		memset(mmin,0,sizeof(mmin));
		memset(zx,0,sizeof(zx));
		tot=1,latans=0;
		n=read(),m=read();
		rg int aa,bb,cc,dd;
		for(rg int i=1;i<=m;i++){
			aa=read(),bb=read(),cc=read(),dd=read();
			jl[i]=Node(aa,bb,dd);
			ad(aa,bb,cc),ad(bb,aa,cc);
		}	
		dij();
		cnt=n;
		std::sort(jl+1,jl+m+1,cmp);
		for(rg int i=1;i<=n+n;i++) fa[i]=i;
		for(rg int i=1;i<=n+n;i++) g[i].clear();
		for(rg int i=1;i<=m;i++){
			aa=jl[i].zb,bb=jl[i].yb,cc=jl[i].val;
			aa=zhao(aa),bb=zhao(bb);
			if(aa==bb) continue;
			val[++cnt]=cc;
			fa[aa]=fa[bb]=cnt;
			g[cnt].push_back(aa),g[cnt].push_back(bb);
		}
		dfs(cnt,0);
		q=read(),k=read(),s=read();
		for(rg int i=1;i<=q;i++){
			aa=read(),bb=read();
			aa=(aa+k*latans-1)%n+1;
			bb=(bb+k*latans)%(s+1);
			printf("%d\n",latans=solve(aa,bb));
		}
	}
	return 0;
}

P4197 Peaks

题目传送门

分析

还是 \(kruskal\) 重构树的板子题

按照边权从小到大排序构建重构树

查询的时候只需要在祖先节点对应的主席树里查询 \(k\) 大就行了

因为只有询问子树的操作,所以可以按照 \(dfn\) 序进行处理

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=4e5+5,maxm=5e5+5;
int h[maxn],tot=1,fa[maxn],n,m,q,val[maxn],cnt,hig[maxn];
struct Node{
	int zb,yb,val;
	Node(){}
	Node(rg int aa,rg int bb,rg int cc){
		zb=aa,yb=bb,val=cc;
	}
}jl[maxm];
bool cmp(rg Node aa,rg Node bb){
	return aa.val<bb.val;
}
struct asd{
	int to,nxt;
}b[maxn<<1];
void ad(rg int aa,rg int bb){
	b[tot].to=bb;
	b[tot].nxt=h[aa];
	h[aa]=tot++;
}
int zhao(rg int xx){
	if(xx==fa[xx]) return xx;
	return fa[xx]=zhao(fa[xx]);
}
int zx[maxn][22],mmax[maxn][22],dep[maxn],rt[maxn],rtcnt;
struct trr{
	int lch,rch,siz;
}tr[maxn*50];
int ad(rg int da,rg int pre,rg int l,rg int r,rg int wz){
	da=++rtcnt;
	tr[da]=tr[pre];
	tr[da].siz++;
	if(l==r) return da;
	rg int mids=(l+r)>>1;
	if(wz<=mids) tr[da].lch=ad(tr[da].lch,tr[pre].lch,l,mids,wz);
	else tr[da].rch=ad(tr[da].rch,tr[pre].rch,mids+1,r,wz);
	return da;
}
int cx(rg int da,rg int pre,rg int l,rg int r,rg int kth){
	if(l==r) return l;
	rg int mids=(l+r)>>1,nsiz=tr[tr[da].rch].siz-tr[tr[pre].rch].siz;
	if(nsiz>=kth) return cx(tr[da].rch,tr[pre].rch,mids+1,r,kth);
	else return cx(tr[da].lch,tr[pre].lch,l,mids,kth-nsiz);
}
int getlca(rg int xx,rg int yy){
	if(dep[xx]<dep[yy]) std::swap(xx,yy);
	rg int len=dep[xx]-dep[yy],k=0;
	while(len){
		if(len&1) xx=zx[xx][k];
		k++,len>>=1;
	}
	if(xx==yy) return xx;
	for(rg int i=20;i>=0;i--){
		if(zx[xx][i]!=zx[yy][i]){
			xx=zx[xx][i],yy=zx[yy][i];
		}
	}
	return zx[xx][0];
}
int dfn[maxn],dfnc,siz[maxn],rk[maxn],sta[maxn],tp;
void dfs(rg int now,rg int lat){
	dep[now]=dep[lat]+1;
	zx[now][0]=lat;
	mmax[now][0]=val[lat];
	dfn[now]=++dfnc;
	rk[dfnc]=now;
	siz[now]=1;
	for(rg int i=1;(1<<i)<=dep[now];i++){
		zx[now][i]=zx[zx[now][i-1]][i-1];
		mmax[now][i]=std::max(mmax[now][i-1],mmax[zx[now][i-1]][i-1]);
	}
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==lat) continue;
		dfs(u,now);
		siz[now]+=siz[u];
	}
}
int zhao(rg int now,rg int val){
	for(rg int i=20;i>=0;i--){
		if(mmax[now][i]<=val && zx[now][i]){
			now=zx[now][i];
		}
	}
	return now;
}
int solve(rg int xx,rg int yy,rg int kth){
	rg int lca=zhao(xx,yy);
	if(tr[rt[dfn[lca]+siz[lca]-1]].siz-tr[rt[dfn[lca]-1]].siz<kth) return -1;
	return sta[cx(rt[dfn[lca]+siz[lca]-1],rt[dfn[lca]-1],1,tp,kth)];
}
int main(){
	memset(mmax,0x3f,sizeof(mmax));
	memset(h,-1,sizeof(h));
	n=read(),m=read(),q=read();
	for(rg int i=1;i<=n;i++) hig[i]=read();
	for(rg int i=1;i<=n;i++) sta[++tp]=hig[i];
	std::sort(sta+1,sta+1+tp);
	tp=std::unique(sta+1,sta+1+tp)-sta-1;
	for(rg int i=1;i<=n;i++) hig[i]=std::lower_bound(sta+1,sta+1+tp,hig[i])-sta;
	cnt=n;
	rg int aa,bb,cc;
	for(rg int i=1;i<=m;i++){
		aa=read(),bb=read(),cc=read();
		jl[i]=Node(aa,bb,cc);
	}
	std::sort(jl+1,jl+1+m,cmp);
	for(rg int i=1;i<=n+n;i++) fa[i]=i;
	for(rg int i=1;i<=m;i++){
		aa=jl[i].zb,bb=jl[i].yb,cc=jl[i].val;
		aa=zhao(aa),bb=zhao(bb);
		if(aa==bb) continue;
		val[++cnt]=cc;
		fa[aa]=cnt,fa[bb]=cnt;
		ad(aa,cnt),ad(cnt,aa);
		ad(bb,cnt),ad(cnt,bb);
	}
	for(rg int i=1;i<=cnt;i++){
		if(fa[i]==i){
			dfs(i,0);
		}
	}
	for(rg int i=1;i<=cnt;i++){
		rt[i]=rt[i-1];
		if(rk[i]<=n){
			rt[i]=ad(rt[i],rt[i],1,tp,hig[rk[i]]);
		}
	}
	for(rg int i=1;i<=q;i++){
		aa=read(),bb=read(),cc=read();
		printf("%d\n",solve(aa,bb,cc));
	}
	return 0;
}

EF Core 6.0的新计划

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

RWCTF2020 DBaaSadge 复现

2021-1-19 23:54:00

经验教程

一. SpringCloud简介与微服务架构

2021-1-20 8:21:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索