洛谷 - P4768 [NOI2018]归程(Kruskal重构树+树上倍增+最短路)

题目链接：点击查看

题目大意：去原网址看吧

题目分析：因为是在刷克鲁斯卡尔重构树的题目，所以稍微思考一下就能想出解法了，首先如果水位线固定了，剩下的边组成的最小生成树也是一定的，此时同一个连通块内的点对答案的贡献都是相同的，因为车子可以随便开，这样连通块的贡献，就是连通块内距离点 1 最近的点了

这样如何找相应的连通块呢？可以对所有边降序排序，建立克鲁斯卡尔重构树，对于点 x 来说，找到权值大于水位线，且深度最小的祖先，这一步可以用树上倍增来完成，此时这个祖先的子树中的点两两都可以互相达到了，显然包括了点 x ，只需要求出这些点中距离点 1 最近的点就好了

至于如何求出某个点的子树中，距离点 1 最近的点，这个预先跑一下迪杰斯特拉，在重构树建好后，在树上跑一边 dfs 就好了

相对于上一道题目来说比较简单，好多代码直接复用下来的（懒）：https://blog.csdn.net/qq_45458915/article/details/108187207

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;
 
const int inf=0x3f3f3f3f;
 
const int N=4e5+100;

const int M=8e5+100;

template<typename T>
struct Dij
{
	const static int N=4e5+100;
	const static int M=8e5+100;
	struct Edge
	{
		int to,next;
		T w;
	}edge[M];
	 
	int head[N],cnt;//链式前向星 
	
	T d[N];
	 
	bool vis[N];
	 
	void addedge(int u,int v,T w)
	{
		edge[cnt].to=v;
		edge[cnt].w=w;
		edge[cnt].next=head[u];
		head[u]=cnt++;
	}
	 
	struct Node
	{
		int to;
		T w;
		Node(int TO,T W)
		{
			to=TO;
			w=W;
		}
		bool operator<(const Node& a)const
		{
			return w>a.w;
		}
	};
	 
	void Dijkstra(int st)
	{
		priority_queue<Node>q;
		memset(vis,false,sizeof(vis));
		memset(d,0x3f,sizeof(d));
		d[st]=0;
		q.push(Node(st,0));
		while(q.size())
		{
			Node cur=q.top();
			int u=cur.to;
			q.pop();
			if(vis[u])
				continue;
			vis[u]=true;
			for(int i=head[u];i!=-1;i=edge[i].next)//扫描出所有边 
			{
				int v=edge[i].to;
				T w=edge[i].w;
				if(d[v]>d[u]+w)//更新 
				{
					d[v]=d[u]+w;
					q.push(Node(v,d[v]));
				}
			}
		}
	}
	 
	void init()
	{
		memset(head,-1,sizeof(head));
		cnt=0; 
	}
};

Dij<int>dij;

int n,m,limit,dp[N][25],f[N],ans[N],val[N];

struct Edge
{
	int u,v,w,h;
	bool operator<(const Edge& t)const
	{
		return h>t.h;
	}
}edge[N];

vector<int>node[N];

void dfs(int u,int fa)
{
	ans[u]=dij.d[u];
	dp[u][0]=fa;
	for(int i=1;i<=limit;i++)
		dp[u][i]=dp[dp[u][i-1]][i-1];
	for(auto v:node[u])
	{
		if(v==fa)
			continue;
		dfs(v,u);
		ans[u]=min(ans[u],ans[v]);
	}
}
/*并查集+克鲁斯卡尔重构树*/
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
 
void Ex_Kruskal()
{
	int index=n;
	for(int i=1;i<=n<<1;i++)
		f[i]=i;
	sort(edge+1,edge+1+m);
	for(int i=1;i<=m;i++)
	{
		int xx=find(edge[i].u),yy=find(edge[i].v);
		if(xx!=yy)
		{
			f[xx]=f[yy]=++index;
			val[index]=edge[i].h;
			node[index].push_back(xx);
			node[index].push_back(yy);
		}
	}
}
/*并查集+克鲁斯卡尔重构树*/
int get_pos(int u,int up)//树上倍增找满足的祖先 
{
	for(int i=20;i>=0;i--)
		if(dp[u][i]!=0&&val[dp[u][i]]>up)
			u=dp[u][i];
	return u;
}

void init(int n)
{
	for(int i=1;i<=n<<1;i++)
		node[i].clear();
	limit=log2(n)+1;
	dij.init();
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int w;
	cin>>w;
	while(w--)
	{
		scanf("%d%d",&n,&m);
		init(n);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w,&edge[i].h);
			dij.addedge(edge[i].u,edge[i].v,edge[i].w);
			dij.addedge(edge[i].v,edge[i].u,edge[i].w);
		}
		dij.Dijkstra(1);
		Ex_Kruskal();
		dfs(find(1),0);
		int q,k,s,last=0;
		scanf("%d%d%d",&q,&k,&s);
		while(q--)
		{
			int v,p;
			scanf("%d%d",&v,&p);
			v=(v+k*last-1)%n+1;
			p=(p+k*last)%(s+1);
			v=get_pos(v,p);
			printf("%d\n",last=ans[v]);
		}
	}







   return 0;
}

 

本文地址：https://blog.csdn.net/qq_45458915/article/details/108188519