[NOI2018]归程题解

Problem

给出一个有\(n\)个点，\(m\)条边的无向联通图，边有长度，海拔两个属性。给出\(Q\)个独立的询问，每次询问给出起点\(u\)，水位线\(p\)，当一条边的海拔不大于水位线时，这条边是有积水的。在\(u\)点时有一辆车，车不能通过有积水的边，你可以在任意节点下车，且下车后不能再次上车，问从\(u\)到\(1\)最小的步行长度。多组数据，强制在线。

Solution

容易发现，当水位线确定了，图会被分成若干个连通块，连通块里的点可以互相到达，故连通块内点的答案为其中的点到\(1\)的距离的最小值，这个可以先\(Dijkstra\)预处理求出（\(spfa\)死了）。

那考虑怎么维护连通块。可持久化并查集？感觉不好搞，有一种神奇的算法——\(Kruscal\)重构树。

其实就是\(Kruscal\)求最小生成树时，每一次合并两个点都建一个新点，新点的点权被赋值为两点间边的边权，并使其成为两个点新的父亲。这颗树有个优秀的性质——这是一个二叉堆。

先按海拔从大到小把边排序，再建出\(Kruscal\)重构树，把新点的点权赋值为边的海拔。这样，从根到叶节点，点权，即海拔是单调递增的，并且每一个点的点权都小于其子树内的点权。

有了这个，我们可以先dfs求出子树内叶子节点到\(1\)距离的最小值，之后从给定的\(u\)树上倍增跳至\(u\)的祖先\(v\)，满足\(v\)的海拔大于给定的\(p\)，点\(v\)子树内的所有叶子节点即是满足条件的连通块内的点。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,q,k,s,cnt,tot,last;
int head[400005],w[800005],to[800005],Next[800005];
int h[400005],fa[400005],vis[400005],dis[400005],Anc[400005][25];

struct Edge{

    int u,v,w,h;

    inline bool operator < (const Edge &x)const{
        return h>x.h;
    }

}E[400005];

struct Node{
    
    int u,dis;

    inline bool operator < (const Node &x)const{
        return dis>x.dis;
    }

};

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
       if(ch=='-')f=-1;
       ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
       x=(x<<1)+(x<<3)+ch-'0';
       ch=getchar();
    }
    return x*f;
}

inline void add(int u,int v,int p){
    w[++cnt]=p;to[cnt]=v;Next[cnt]=head[u];head[u]=cnt;
}

inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void dfs(int u,int f){
    Anc[u][0]=f;
    for(register int i=1;i<=20;++i)
        Anc[u][i]=Anc[Anc[u][i-1]][i-1];
    for(register int i=head[u];i;i=Next[i]){
        int v=to[i];
        dfs(v,u);
        dis[u]=min(dis[u],dis[v]);
    }
    return;
}

int query(int u,int x){
    for(register int i=20;~i;--i){
        if(h[Anc[u][i]]>x)
            u=Anc[u][i];
    }
    return dis[u];
}

void Dijkstra(){
    priority_queue<Node>q;
    memset(vis,0   ,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    q.push((Node){1,0});dis[1]=0;
    while(!q.empty()){
        Node u=q.top();q.pop();
        if(vis[u.u])
            continue;
        vis[u.u]=1;
        for(register int i=head[u.u];i;i=Next[i]){
            int v=to[i];
            if(dis[v]>dis[u.u]+w[i]){
                dis[v]=dis[u.u]+w[i];
                if(!vis[v])
                    q.push((Node){v,dis[v]});
            }
        }
    }
    return;
}

void Kruscal(){

    tot=n;cnt=0;
    memset(head,0,sizeof head);

    sort(E+1,E+m+1);

    for(register int i=1;i<=n;++i)
        fa[i]=i,fa[i+n]=i+n;
    
    for(register int i=1;i<=m;++i){
        int u=E[i].u,v=E[i].v;
        if(find(u)!=find(v)){
            int fu=find(u),fv=find(v);
            fa[fu]=fa[fv]=++tot;
            h[tot]=E[i].h;
            add(tot,fu,0);
            add(tot,fv,0);
        }
        if(tot==n+n-1)
            break;
    }

    dfs(tot,0);

    return;
}

void work(){

    memset(head,0,sizeof head);

    cnt=0;n=read();m=read();

    for(register int i=1;i<=m;++i){
        E[i]=(Edge){read(),read(),read(),read()};
        add(E[i].u,E[i].v,E[i].w);
        add(E[i].v,E[i].u,E[i].w);
    }

    Dijkstra();Kruscal();

    last=0;q=read();k=read();s=read();

    for(register int i=1;i<=q;++i){
        int u=(read()+k*last-1)%n+1;
        int p=(read()+k*last)%(s+1);
        printf("%d\n",last=query(u,p));
    }

    return;
}

int main(){

    int T=read();
    
    while(T--)
        work();
    
    return 0;
}