hello.

题解 P4768 【[NOI2018]归程】

2018-07-24 15:58:45


思路

这道题作为签到题思路还是非常简单的。把没有积水开车可以相互抵达的点并查集合并,同时维护一个“联通块”里走路到终点的最短路径。题目要求在线,那就用可持久化并查集。

初始状态是每个点相互独立,我们按海拔从高到低的顺序依次合并边的入点和出点,询问的时候二分一下版本直接在主席树里查找就可以。

代码的话,理解了思路是比较好打的,就是很多细节需要注意。建议在写这道题之前先 AC 【模板】可持久化并查集

首发于个人博客

代码

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define maxn 400010
#define minn(a,b) a<b?a:b
#define maxx(a,b) a>b?a:b 
using namespace std;
int root[maxn],head[maxn],dis[maxn],n,m,cnt,cnt_e;
struct Edge{
    int to,next,val,lev;
    Edge(int a=0,int b=0,int c=0,int d=0){
        to=a,next=b,val=c,lev=d;
    }
}l[maxn<<2];//储存原图
struct Sp_Edge{
    int from,to,lev;
    Sp_Edge(int a=0,int b=0,int c=0){
        from=a,to=b,lev=c;
    }
    bool operator < (const Sp_Edge &x) const{
        return lev>x.lev;
    }
}e[maxn<<2];//用于排序和并查集合并
struct Node{
    int f,p,d;
    Node(int a=0,int b=0,int c=0){
        f=a,p=b,d=c;
    }
};//主席树节点
struct PT{
    int ls[maxn*44],rs[maxn*44],now;
    Node tree[maxn*44],ins;
    void ctl(int f,int p,int d){
        ins=Node(f,p,d);
    }//要插入的信息
    inline int build(int l,int r){
        int o=++now;
        if (l==r){
            tree[o]=Node(l,1,dis[l]);
            return o;
        }
        ls[o]=build(l,mid);
        rs[o]=build(mid+1,r);
        return o;
    }
    inline int insert(int pre,int l,int r,int x){
        int o=++now;
        tree[o]=tree[pre];
        ls[o]=ls[pre],rs[o]=rs[pre];
        if (l==r){
            tree[o]=ins;
            return o;
        }
        if (x<=mid) ls[o]=insert(ls[pre],l,mid,x);
            else rs[o]=insert(rs[pre],mid+1,r,x);
        return o;
    }
    inline Node query(int o,int l,int r,int x){
        if (l==r) return tree[o];
        if (x<=mid) return query(ls[o],l,mid,x);
        else return query(rs[o],mid+1,r,x);
    }
    inline void reset(){
        memset(ls,0,sizeof(ls));
        memset(rs,0,sizeof(rs));
        memset(tree,0,sizeof(tree));
        now=0;
    }
}ds;//主席树基本操作
struct d_node{
    int v,d;
    d_node(int a=0,int b=0){
        v=a,d=b;
    }
    bool operator < (const d_node &x) const{
        return d>x.d;
    }
};//用于堆优化 Dijistra
inline void Dijstra(){
    int vis[maxn];
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<d_node>q;
    q.push((d_node){1,0});
    dis[1]=0;
    while(!q.empty()){
        d_node hq=q.top();q.pop();
        if (vis[hq.v]) continue;
        vis[hq.v]=1;
        for (register int i=head[hq.v];i;i=l[i].next){
            int v=l[i].to;if (vis[v]) continue;
            if (dis[v]>dis[hq.v]+l[i].val)
            dis[v]=dis[hq.v]+l[i].val,q.push((d_node){v,dis[v]});
        }
    }
}
inline void Add(int fr,int to,int dis,int lev){
    l[++cnt]=Edge(to,head[fr],dis,lev);
    head[fr]=cnt;
    l[++cnt]=Edge(fr,head[to],dis,lev);
    head[to]=cnt;
    e[++cnt_e]=Sp_Edge(fr,to,lev);
}
inline int search(int x){
    int l=1,r=m,res=0;
    while(l<=r){
        if (e[mid].lev>x)
            res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}//二分查找版本
inline int find(int now,int x){
    Node tem=ds.query(root[now],1,n,x);
    int fx=tem.f;
    if (fx==x) return x;
    return find(now,fx);
}//不能路径压缩
inline void merge(int now,int x,int y){
    int fx=find(now,x),fy=find(now,y);
    if (fx==fy) return;
    Node infx=ds.query(root[now],1,n,fx);
    Node infy=ds.query(root[now],1,n,fy);
    if (infx.p>=infy.p) swap(infx,infy),swap(fx,fy);//按深度合并
    ds.ctl(fy,infx.p,infx.d);
    root[now]=ds.insert(root[now],1,n,fx);
    ds.ctl(infy.f,maxx(infx.p+1,infy.p),minn(infx.d,infy.d));
    root[now]=ds.insert(root[now],1,n,fy);
}
inline void Solve(){
    cin>>n>>m;
    int x,y,z,w,v0,p0;
    for (register int i=1;i<=m;i++){
        cin>>x>>y>>z>>w;
        Add(x,y,z,w);
    }
    Dijstra();//预处理最短路
    sort(e+1,e+1+m);
    root[0]=ds.build(1,n);
    for (register int i=1;i<=m;i++){
        root[i]=root[i-1];
        merge(i,e[i].from,e[i].to);
    }//按海报高度合并
    int q,k,s,lastans=0;
    cin>>q>>k>>s;
    for (register int i=1;i<=q;i++){
        cin>>v0>>p0;
        v0=(v0+k*lastans-1)%n+1;
        p0=(p0+k*lastans)%(s+1);
        int pos=search(p0);
        int loc=find(pos,v0);
        Node tem=ds.query(root[pos],1,n,loc);
        lastans=tem.d;
        printf("%d\n",lastans);
    }
}
inline void Reset(){
    memset(root,0,sizeof(root));
    memset(head,0,sizeof(head));
    memset(l,0,sizeof(l));
    memset(e,0,sizeof(e));
    n=0,m=0,cnt=0,cnt_e=0;
    ds.reset();
}
int main(){
    int T;
    cin>>T;
    for (int i=1;i<=T;i++){
        Solve();
        if (i==T) break;
        Reset();
    }
    return 0;
}