P4768 [NOI2018]归程（kruskal 重构树）

洛谷P4768 [NOI2018]归程

 LOJ#2718.「NOI2018」归程

用到 kruskal 重构树，所以先说这是个啥

显然，这和 kruskal 算法有关系（废话

这个重构树是一个有点权的树

以最小生成树为例，当然最大也一样

先把所有原有的节点点权赋为 \(0\)

在跑 kruskal 的时候，我们没求出一条当前权值最小，且两端点不在同一集合的边时（并查集，kruskal 常规操作），我们就选这条边，然后把两端点划分在同一集合

不过上面仅仅时 kruskal 的操作，另外，我们还要在新建一个节点，把这个新节点作为父亲，这条被选择的边的两个端点，在并查集中的根，就是他的两个儿子

新建节点的点权，就是当前选的这条边的边权

然后合并集合的时候，要把新建的这个节点，和两个端点都合并在一个集合中，并且，把新建节点作为根（根说的就是并查集的最早祖先）

这样，以节点 \(x\) 为根的集合中的所有点，都在以 \(x\) 为根的树上

这样，每选择一条边，都会新建一个集合（就是新的那个节点，这个节点的集合一建立就被和其它的合并了，但是不妨还是理解为先建立），合并三个集合，也就是集合总数少了一个

那么选 \(n-1\) 条边（显然这就是最小生成树上的所有边），就会得到一个集合，这个集合的根就是重构树的根，如果从 \(n+1\) 开始为新建的节点编号，那么根的编号就是 \(2n-1\)

此时，新构建出的这个树，就是 kruskal 重构树

举个栗子，有如下一张图

它的最小生成树是这样的：

那么它的重构树是这样的

考虑一下它有哪些性质

是一棵二叉树，并且每个非叶子节点都有两个儿子，观察刚才构建原则，很显然
一个节点在重构树中是叶子节点，等价于这个节点是原有的节点，也很显然
在树上的任意一条上下的链上（直上直下，不能在中间某个节点拐弯），如果是在求最小生成树时重构的，点权从下到上不减，如果时求最大生成树时重构的，不考虑叶子节点，是不增

这点是很显然的，以最小生成树为例，我们总是先选择权值小的边，创建的点的点权小，然后没次新创建的点，总是在已经创建的（或者原有的）点的上面，所以一条链上总是上面的点点权更大（或相同）
容易发现，最小生成树上两个点之间，树上路径中，最大边权就是重构树中，两点 LCA 的点权（最大生成树中最小边权也一样，下面就不再分类说了）
通过上一条，可以知道，到节点 \(v\) 的树上路径中的最大值，小于某个值的所有节点 \(u\)，都在同一个子树内

再由第二条性质，都是这个子树内的叶子节点
由上一条继续推，就能知道，这个子树的根，就是从 \(v\) 到整个重构树的根的路径中，深度最小的，点权小于这个值的节点

一般来说，又因为这个路径上的点圈不减，所以这个节点可以预处理一个倍增数组，来求出，下面要说的那个题就用到这个方法

基本上就是这些了，下面来看 [NOI2018]归程这题

kruskal 重构树+倍增+dij 最短路

不算太难，当kruskal 重构树上手题比较好

话说当年应该就是这题宣布了 SPFA 的死亡（（（

由于开车只能走海拔比某个值大的边，所以我们应该按照海拔，给原图求一个最大生成树的 kruskal 重构树

由上面的性质，可以 \(\log n\) 内求出所有开车能达到的节点，都在重构树中哪个节点的子树中

因为要求走路走的最短，所以用 SPFA 用 dijkstra 求出 \(1\) 到每个点的最短路（按照长度）

然后，在对重构树进行预处理 dfs 时，不光要求出倍增数组，还要求出当前节点 \(u\) 的子树中，到 \(1\) 的最短路最小的点的最短路长度

所以，用倍增跳到从起点，到整个重构树的根的路径中，深度最小的，点权大于这个值（就是水位线）的节点

然后答案就是这个点的子树中，到 \(1\) 的最短路径长度

然后，就做完了，我会做noi2018的题了，耶

自己犯的傻：

多测不清零，5分两行泪

数组没二倍（重构树有 \(2n-1\) 个节点），50分两行泪

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<map>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	register int x=0;register int y=1;

	register char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

#define N 200006

#define M 800006

int n,m,vertex;

inline int get_min(int x,int y){return x<y?x:y;}

struct graph{

	int fir[N],nex[M],to[M],w[M],tot;

	inline void add(int u,int v,int len){

		to[++tot]=v;w[tot]=len;

		nex[tot]=fir[u];fir[u]=tot;

	}

	inline void clear(){

		std::memset(fir,0,sizeof fir);std::memset(nex,0,sizeof nex);

		tot=0;

	}

}G;

struct shortest_path{

	int dis[N],heap[N],size,in[N];

	inline void push(int x){

		heap[++size]=x;

		reg int i=size,fa;

		while(i>1){

			fa=i>>1;

			if(dis[heap[fa]]<=dis[heap[i]]) return;

			std::swap(heap[fa],heap[i]);i=fa;

		}

	}

	inline int pop(){

		int ret=heap[1];heap[1]=heap[size--];

		int i=1,ls,rs;

		while((i<<1)<=size){

			ls=i<<1;rs=ls|1;

			if(rs<=size&&dis[heap[rs]]<dis[heap[ls]]) ls=rs;

			if(dis[heap[ls]]>=dis[heap[i]]) break;

			std::swap(heap[i],heap[ls]);i=ls;

		}

		return ret;

	}

	inline void dij(int start){

		std::memset(dis,0x3f,sizeof dis);dis[start]=0;

		push(start);in[start]=1;

		while(size){

			reg int u=pop();in[u]=0;

			for(reg int v,i=G.fir[u];i;i=G.nex[i]){

				v=G.to[i];

				if(dis[v]>dis[u]+G.w[i]){

					dis[v]=dis[u]+G.w[i];

					if(!in[v]) push(v),in[v]=1;

				}

			}

		}

	}

}path;

struct kruskal_tree{

	struct edge{

		int u,v,w;

	}e[M];

	inline int find(int k){

		return k==up[k]?k:up[k]=find(up[k]);

	}

	static inline int cmp(edge aa,edge aaa){return aa.w>aaa.w;}

	int up[N*2],son[2][N*2],val[N*2];

	int fa[23][N*2],min_dis[N*2];

	inline void kruskal(){

		std::sort(e+1,e+1+m,cmp);

		vertex=n;

		for(reg int i=1;i<n*2;i++) up[i]=i;

		for(reg int u,v,i=1,cnt=1;cnt<n;i++){

			u=find(e[i].u);v=find(e[i].v);

			if(u==v) continue;

			val[++vertex]=e[i].w;

			son[0][vertex]=u;son[1][vertex]=v;

			cnt++;up[u]=up[v]=vertex;

		}

	}

	void dfs(int u){

//			std::printf("now : %d\n",u);

		for(reg int i=1;i<20;i++) fa[i][u]=fa[i-1][fa[i-1][u]];

		min_dis[u]=u<=n?path.dis[u]:0x3f3f3f3f;

		if(son[0][u]){

			fa[0][son[0][u]]=u;

			dfs(son[0][u]);

			min_dis[u]=get_min(min_dis[u],min_dis[son[0][u]]);

		}

		if(son[1][u]){

			fa[0][son[1][u]]=u;

			dfs(son[1][u]);

			min_dis[u]=get_min(min_dis[u],min_dis[son[1][u]]);

		}

	}

	inline int get_min_dis(reg int u,reg int p){

		for(reg int i=19;~i;i--)

			if(val[fa[i][u]]>p) u=fa[i][u];

		return min_dis[u];

	}

}TREE;

inline void clear(){

	std::memset(TREE.fa,0,sizeof TREE.fa);std::memset(TREE.min_dis,0,sizeof TREE.min_dis);

	std::memset(TREE.val,0,sizeof TREE.val);std::memset(TREE.son,0,sizeof TREE.son);

	G.clear();

//		std::puts("\n\n---------------------------------------------\n\n");

}

int main(){

//	std::freopen("return.in","r",stdin);

//	std::freopen("return.out","w",stdout);

int CASES=read();while(CASES--){

	n=read();m=read();

	for(reg int w,i=1;i<=m;i++){

		TREE.e[i].u=read();TREE.e[i].v=read();w=read();TREE.e[i].w=read();

		G.add(TREE.e[i].u,TREE.e[i].v,w);G.add(TREE.e[i].v,TREE.e[i].u,w);

	}

	path.dij(1);

	TREE.kruskal();

	TREE.fa[0][vertex]=vertex;TREE.dfs(vertex);

	int q=read(),K=read(),S=read();

	reg int lastans=0,u,p;

	while(q--){

		u=(read()+(LL)K*lastans-1)%n+1;p=(read()+(LL)K*lastans)%(S+1);

		lastans=TREE.get_min_dis(u,p);

		std::printf("%d\n",lastans);

	}

	if(CASES) clear();

}

	return 0;

}

巴特西

P4768 [NOI2018]归程（kruskal 重构树）

最新文章

热门文章