并不对劲的bzoj5415:loj2718:uoj393:p4768:[NOI2018]归程-白红宇

并不对劲的bzoj5415:loj2718:uoj393:p4768:[NOI2018]归程

阅读量：4501 次

发布时间：2019-06-08

本文共 3117 字，大约阅读时间需要 10 分钟。

题目大意

\(n\)(\(n\leq2*10^5\))个点，\(m\)(\(m\leq4*10^5\))条边的图，每条边有海拔\(a_i(a_i\leq10^9)\)、长度\(l_i(l_i\leq10^4)\)，定义两点\(a,b\)距离为从\(a\)走到\(b\)至少要走的长度之和

\(q\)组询问，强制在线，每次给出\(v,p\)，表示询问不走\(a_i\leq p\)的边，从\(v\)出发能走到的与\(1\)号点距离最近的点到\(1\)号点的距离

题解

预处理每个点到\(1\)号点的距离

每次询问相当于在问删掉所有\(a_i\leq p\)的边，点\(v\)所在连通块中到\(1\)号点最小的距离

发现只考虑原图的最大生成树上的边，不会改变连通性

点\(v\)所在连通块之所以到不了别的点集，是因为它们之间在最大生成树上的路径中有一条边\(a_i\leq p\)

考虑kruskal的过程，相当于有一次是用一条\(a_i\leq p\)的边合并了点\(v\)所在连通块与其他点集

这样就可以以这种方法建一新棵树：一开始有\(n\)个点，没有边，kruskal中每合并两个点集，就新建一个表示当前边的点，并且将两个点集新树中的根变成新建点的儿子

新树中一个点的子树表示这个点对应的原图的最大生成树中一条边kruskal时合并的两个点集，也就是说，这个子树中任意两点的路径中不会出现边权小于该边的边

所以每次询问在新树中找\(v\)的深度最小的\(a_i> p\)的祖先

这个新树也叫kruskal重构树

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #define rep(i,x,y) for(register int i=(x);i<=(y);++i)#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)#define view(u,k) for(int k=fir[u];~k;k=nxt[k])#define maxn 200010#define maxm 800010#define pii pair
                 
                  #define fi first#define se second#define mp make_pair#define LL long longusing namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)&&ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); return x*f;}void write(int x){ if(x==0){putchar('0'),putchar('\n');return;} int f=0;char ch[20]; if(x<0)putchar('-'),x=-x; while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n'); return;}int t,n,m,fir[maxn],nxt[maxm],v[maxm],w[maxm],fa[maxn],anc[maxn<<1][20],val[maxn<<1],mind[maxn<<1],ans;int cnte,cntnd,dis[maxn],vis[maxn],q,k,s;struct edge{int u,v,w;}e[maxm>>1];void ade(int u1,int v1,int w1){v[cnte]=v1,w[cnte]=w1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}priority_queue
                  
                   Q;bool cmp(edge x,edge y){return x.w>y.w;}void reset(){ rep(i,1,n)fa[i]=-i,fir[i]=-1,dis[i]=2147483647,vis[i]=0; rep(i,1,(n<<1)){val[i]=0,mind[i]=2147483647;rep(j,0,19)anc[i][j]=0;}ans=0; cnte=0,cntnd=n;}int f(int x){return fa[x]<0?x:fa[x]=f(fa[x]);}int main(){ t=read(); while(t--) { n=read(),m=read(); reset(); rep(i,1,m){int x=read(),y=read(),l=read(),a=read();ade(x,y,l),ade(y,x,l),e[i].u=x,e[i].v=y,e[i].w=a;} sort(e+1,e+m+1,cmp); dis[1]=0;Q.push(mp(0,1)); while(!Q.empty()) { int u=Q.top().se;Q.pop(); if(vis[u])continue;vis[u]=1; view(u,k)if(dis[v[k]]>dis[u]+w[k]) { dis[v[k]]=dis[u]+w[k]; if(!vis[v[k]])Q.push(mp(-dis[v[k]],v[k])); } } rep(i,1,n)mind[i]=dis[i]; rep(i,1,m) { int x=f(e[i].u),y=f(e[i].v); if(x!=y) { cntnd++,val[cntnd]=e[i].w,anc[-fa[x]][0]=anc[-fa[y]][0]=cntnd,mind[cntnd]=min(mind[-fa[x]],mind[-fa[y]]); fa[x]=y,fa[y]=-cntnd; } } dwn(i,cntnd,1){rep(j,1,19)anc[i][j]=anc[anc[i][j-1]][j-1];} q=read(),k=read(),s=read(); while(q--) { int u=read(),p=read(),tu; u=(u+k*ans-1)%n+1,p=((LL)p+(LL)k*ans)%(LL)(s+1),tu=u; dwn(i,19,0)if(anc[tu][i]&&val[anc[tu][i]]>p)tu=anc[tu][i]; write(ans=mind[tu]); } } return 0;}/*24 31 2 50 12 3 100 23 4 50 15 0 23 02 14 13 13 24 31 2 50 12 3 100 23 4 50 15 0 23 02 14 13 13 2*/

转载于:https://www.cnblogs.com/xzyf/p/10492055.html

你可能感兴趣的文章