[洛谷 4768,loj 2718][NOI2018]归程

题目链接

https://www.luogu.com.cn/problem/P4768

https://loj.ac/problem/2718

题解

本题需要用到一个叫 Kruskal 重构树 的东西。

我们首先分析一下这道题:首先给出一个 \(v\),我们需要找到一条 \(v \to p \to 1\) 的路径,满足:

  • \(v \to p\) 的路径全程没有积水(海拔高于水位线);
  • \(p \to 1\) 的路径尽可能短。

先解决第二部分。因为图是无向图,所以我们先预处理出 \(1\) 为起点的单源最短路径(记得不要用某死去的算法)

对于第一部分,我们需要找到任意两点间海拔最低的边最高的一条路径,这个可以通过建立以海拔为边权的最大生成树解决(还记得最大/小生成树一定是瓶颈生成树吗?)。

接下来 Kruskal 重构树就要登场了。

我们在最大生成树上建立重构树,这棵树具有这样的特点:从 \(u\) 到 \(v\) 要经过的最低海拔,正是 \(\text{lca}(u,v)\) 的点权。而且,这棵树还是个小根堆。

也就是说,设水位线为 \(p\),如果 \(u\) 的某个祖先 \(x\) 的点权大于 \(p\),\(u\) 就可以抵达 \(x\) 的所有子节点。

因此我们只需要在所有可以到达的点中,找到距离 \(1\) 号点最近的点即可。

具体来说,我们从根节点开始遍历重构树,遍历到点 \(u\) 的时候,预处理 \(u\) 的子树中到 \(1\) 号点的最短距离。

对于一个起点 \(v\),我们只需倍增向上跳,找到能到达的深度最小的祖先 \(pa\) 即可,则答案就是 \(pa\) 的子树中到 \(1\) 号点的最短距离。

这样我们就完美解决了本题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
struct edge
{
 int v,w,next;
}e[800005];
struct node
{
 int u,v,l,a;
 bool operator<(const node&p)const
 {
  return a>p.a;
 }
}p[400005];
struct dsu
{
 int fa[400005];
 void init(int n)
 {
  for(int i=1;i<=n;i++)
   fa[i]=i;
 }
 int find(int x)
 {
  return fa[x]==x?x:fa[x]=find(fa[x]);
 }
 void set(int x,int y)
 {
  fa[x]=y;
 }
}d;
int head[200005],dis[200005],vis[200005];
int cnt,n,m;
int val[400005],fa[400005][25],mind[400005],dep[400005];
vector<int> tr[400005];
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void dijkstra()
{
 priority_queue<pii,vector<pii>,greater<pii> > q;
 memset(dis,63,sizeof(dis));
 memset(vis,0,sizeof(vis));
 dis[1]=0;
 q.push(make_pair(0,1));
 while(!q.empty())
 {
  int u=q.top().second;
  q.pop();
  if(vis[u])continue;
  vis[u]=1;
  for(int i=head[u];i;i=e[i].next)
  {
   int v=e[i].v;
   if(dis[v]>dis[u]+e[i].w)
   {
    dis[v]=dis[u]+e[i].w;
    q.push(make_pair(dis[v],v));
   }
  }
 }
}
void build_retree()
{
 memset(val,0,sizeof(val));
 for(int i=1;i<=2*n;i++)
 {
  tr[i].clear();
  if(i<=n)mind[i]=dis[i];
  else mind[i]=1<<30;
 }
 cnt=n;
 sort(p+1,p+m+1);
 d.init(2*n);
 for(int i=1;i<=m;i++)
 {
  int u=p[i].u,v=p[i].v;
  int fu=d.find(u),fv=d.find(v);
  if(fu!=fv)
  {
   cnt++;
   val[cnt]=p[i].a;
   d.set(fu,cnt);
   d.set(fv,cnt);
   tr[cnt].push_back(fu);
   tr[cnt].push_back(fv);
  }
 }
}
void dfs(int u,int f)
{
 dep[u]=dep[f]+1;
 fa[u][0]=f;
 for(int i=1;i<=20;i++)
  fa[u][i]=fa[fa[u][i-1]][i-1];
 for(auto v:tr[u])
 {
  dfs(v,u);
  mind[u]=min(mind[u],mind[v]);
 }
}
int main()
{
 ios::sync_with_stdio(false);
 int T;
 cin>>T;
 while(T--)
 {
  cnt=0;
  memset(head,0,sizeof(head));
  memset(dep,0,sizeof(dep));
  memset(fa,0,sizeof(fa));
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
   cin>>p[i].u>>p[i].v>>p[i].l>>p[i].a;
   addedge(p[i].u,p[i].v,p[i].l);
   addedge(p[i].v,p[i].u,p[i].l);
  }
  dijkstra();
  build_retree();
  dfs(cnt,0);
  int Q,K,S,lastans=0;
  cin>>Q>>K>>S;
  while(Q--)
  {
   int v,p;
   cin>>v>>p;
   v=(v+K*lastans-1)%n+1;
   p=(p+K*lastans)%(S+1);
   for(int i=20;i>=0;i--)
    if(dep[v]>(1<<i)&&val[fa[v][i]]>p)v=fa[v][i];
   cout<<(lastans=mind[v])<<endl;
  }
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注