欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-23 09:11:11
题目链接:点击查看题目大意:去原网址看吧题目分析:因为是在刷克鲁斯卡尔重构树的题目,所以稍微思考一下就能想出解法了,首先如果水位线固定了,剩下的边组成的最小生成树也是一定的,此时同一个连通块内的点对答案的贡献都是相同的,因为车子可以随便开,这样连通块的贡献,就是连通块内距离点 1 最近的点了这样如何找相应的连通块呢?可以对所有边降序排序,建立克鲁斯卡尔重构树,对于点 x 来说,找到权值大于水位线,且深度最小的祖先,这一步可以用树上倍增来完成,此时这个祖先的子树中的点两两都可以互相达到了,显然包括...

题目链接:点击查看

题目大意:去原网址看吧

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