【BZOJ5415】【NOI2018】归程（克鲁斯卡尔重构树）

时间：2023-03-09 16:51:03
【BZOJ5415】【NOI2018】归程（克鲁斯卡尔重构树）

【NOI2018】归程（克鲁斯卡尔重构树）

题面

洛谷

题解

我在现场竟然没有把这道傻逼题给切掉，身败名裂。

因为这题就是克鲁斯卡尔重构树的模板题啊

我就直接简单的说一下把

首先发现答案就是在只经过海拔大于\(p\)的边的情况下，所有点到\(1\)号点中最短路最小的那个点。所以预处理最短路径，构建克鲁斯卡尔重构树，直接倍增+线段树就好了。

还有一种基于离线做法的方法。

我们发现离线做法只需要按照所有询问排序，

然后利用并查集按照海拔高度从小往大合并（这个其实就是克鲁斯卡尔）

这样子就可以利用可持久并查集解决。

发现并不需要回朔时间并修改，而只需要查询历史版本的值。

因为每次增加一条边只会修改两个集合，所以可以使用一个\(vector\)存下每个点每次修改之后的父亲以及当前修改的时间，那么每次询问的时候只需要在对应的点上二分查询在目标时间的集合父亲就好了，合并使用启发式合并，保证复杂度是\(O(nlogn+Qlogn)\)。

我的代码是克鲁斯卡尔重构树

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

#define ll long long

#define MAX 200200

#define pir pair<int,int>

#define mpi make_pair

#define fr(x) (x.first)

#define sd(x) (x.second)

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

	int x=0;bool fl=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')fl=true,ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

	return fl?-x:x;

}

struct Edge{int u,v,w,s;}E[MAX<<1];

bool operator<(Edge a,Edge b){return a.s>b.s;}

struct Line{int v,next,w,s;}e[MAX<<2];

int h[MAX<<1],cnt=1;

inline void Add(int u,int v,int w,int s){e[cnt]=(Line){v,h[u],w,s};h[u]=cnt++;}

int n,m,dis[MAX],Q,typ,S;

bool vis[MAX];

namespace SP

{

	priority_queue<pir,vector<pir>,greater<pir> >Q;

	void Dijkstra()

	{

		memset(vis,0,sizeof(vis));

		while(!Q.empty())Q.pop();

		Q.push(mpi(0,1));

		while(!Q.empty())

		{

			pir u=Q.top();Q.pop();

			if(vis[sd(u)])continue;vis[sd(u)]=true;

			dis[sd(u)]=fr(u);

			for(int i=h[sd(u)];i;i=e[i].next)

				if(!vis[e[i].v])Q.push(mpi(dis[sd(u)]+e[i].w,e[i].v));

		}

	}

}

namespace MST

{

	int f[MAX<<1],id;

	int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

	void init(){for(int i=1;i<=n<<1;++i)f[i]=i;id=n;}

	void Kursual()

	{

		init();

		for(int i=1;i<=m;++i)

		{

			int u=getf(E[i].u),v=getf(E[i].v);

			if(u==v)continue;++id;

			Add(id,u,E[i].w,E[i].s);Add(id,v,E[i].w,E[i].s);

			f[u]=f[v]=id;

		}

	}

}

int dfn[MAX<<1],low[MAX<<1],tim,ln[MAX<<1];

int p[20][MAX<<1],s[20][MAX<<1];

void dfs(int u)

{

	if(u<=n)dfn[u]=++tim,ln[tim]=u;else dfn[u]=1e9;

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

	for(int i=1;i<20;++i)s[i][u]=min(s[i-1][u],s[i-1][p[i-1][u]]);

	for(int i=h[u];i;i=e[i].next)

	{

		p[0][e[i].v]=u;s[0][e[i].v]=e[i].s;

		dfs(e[i].v);dfn[u]=min(dfn[u],dfn[e[i].v]);

	}

	low[u]=tim;

}

void init(){memset(h,0,sizeof(h));cnt=1;tim=0;}

int t[MAX<<2];

void Build(int now,int l,int r)

{

	if(l==r){t[now]=dis[ln[l]];return;}

	int mid=(l+r)>>1;

	Build(lson,l,mid);Build(rson,mid+1,r);

	t[now]=min(t[lson],t[rson]);

}

int Query(int now,int l,int r,int L,int R)

{

	if(L<=l&&r<=R)return t[now];

	int mid=(l+r)>>1,ret=2147483647;

	if(L<=mid)ret=min(ret,Query(lson,l,mid,L,R));

	if(R>mid)ret=min(ret,Query(rson,mid+1,r,L,R));

	return ret;

}

int Jump(int u,int r)

{

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

		if(p[i][u]&&s[i][u]>r)u=p[i][u];

	return u;

}

int main()

{

	freopen("return.in","r",stdin);

	freopen("return.out","w",stdout);

	int T=read();

	while(T--)

	{

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

		for(int i=1;i<=m;++i)

		{

			int u=read(),v=read(),l=read(),s=read();

			E[i]=(Edge){u,v,l,s};

			Add(E[i].u,E[i].v,E[i].w,E[i].s);

			Add(E[i].v,E[i].u,E[i].w,E[i].s);

		}

		sort(&E[1],&E[m+1]);

		SP::Dijkstra();init();

		memset(p,0,sizeof(p));memset(s,0,sizeof(s));

		MST::Kursual();dfs(MST::id);

		Build(1,1,n);

		Q=read();typ=read();S=read();

		int lans=0,v,p;

		while(Q--)

		{

			v=(read()+typ*lans-1)%n+1;

			p=(read()+typ*lans)%(S+1);

			v=Jump(v,p);

			printf("%d\n",lans=Query(1,1,n,dfn[v],low[v]));

		}

	}

	return 0;

}

相关文章