首页 > 代码库 > BZOJ4699 : 树上的最短路
BZOJ4699 : 树上的最短路
这道题主要是要解决以下两个问题：
问题1：
给定一个点$x$，如何取出所有经过它的下水道？
一条下水道经过$x$等价于它起点在$x$的子树里面且终点不在$x$的子树里面，或者两端点的lca就是$x$。
对于第一种情况，也就是说起点在$x$的dfs序子区间里，终点小于$st[x]$或者大于$en[x]$。
假设下水道是$A-B$向$C-D$连边，并且$st[A]<st[B]$，
那么只需要不断查询$st[A]$在$[L,R]$里$st[B]$最大的下水道，以及$st[B]$在$[L,R]$里$st[A]$最小的下水道即可。
用线段树按dfs序维护终点$dfn$最小和最大的下水道，然后不断取出即可。
注意到Dijkstra的时候，$dis$不降，所以对于一条下水道，只有$A-B$里第一个被访问到的点才会用到它，所以在使用完毕后直接删除即可。
问题2：
如何求最短路？
考虑转化问题，改成求起点到每条有向边的最短路，这个最短路包括这条边本身的权值。
按距离维护一个小根堆，里面有两种元素：
$1.$某条有向树边$x->y$
$2.$某条下水道$A-B,C-D$
每次取出堆顶元素，如果是树边，那么枚举$y$的出边，同时将经过$y$的下水道都取出即可。
如果是下水道，那么暴力将$C-D$路径上所有没有访问过的点的出边都取出。
因为每个点只需要取一次，所以用并查集完成路经压缩即可。
总时间复杂度$O((n+m)\log n)$，空间复杂度$O(n+m)$。
#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;typedef pair<ll,int>P;const int N=250010,M=100010,T=262150,BUF=12000000,OUT=5000000;char Buf[BUF],*buf=Buf,Out[OUT],*ou=Out;int Outn[30],Outcnt;int n,m,S,i,j,C,D,x,y,z,g[N],v[N<<1],w[N<<1],nxt[N<<1],ed,fa[N],G[N],NXT[M];bool vis[M];int size[N],f[N],d[N],son[N],top[N],dfn,st[N],en[N];int l1[N],r1[N],l2[N],r2[N],ea[M],eb[M],va[T],vb[T],cur,q[99],pos[M],l;ll ans[N];P t,h[N*2+M];struct E{int u,v,z,a,b,c;}e[M];void sorta(int l,int r){ int i=l,j=r,m=e[ea[(l+r)>>1]].a; do{ while(e[ea[i]].a<m)i++; while(e[ea[j]].a>m)j--; if(i<=j)swap(ea[i],ea[j]),i++,j--; }while(i<=j); if(l<j)sorta(l,j); if(i<r)sorta(i,r);}void sortb(int l,int r){ int i=l,j=r,m=e[eb[(l+r)>>1]].b; do{ while(e[eb[i]].b<m)i++; while(e[eb[j]].b>m)j--; if(i<=j)swap(eb[i],eb[j]),i++,j--; }while(i<=j); if(l<j)sortb(l,j); if(i<r)sortb(i,r);}inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}inline void write(ll x){ if(!x)*ou++=48; else{ for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48; while(Outcnt)*ou++=Outn[Outcnt--]; }}inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}inline void ADD(int x,int y){NXT[y]=G[x];G[x]=y;}void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){ f[v[i]]=x,d[v[i]]=d[x]+1; dfs(v[i]),size[x]+=size[v[i]]; if(size[v[i]]>size[son[x]])son[x]=v[i]; }}void dfs2(int x,int y){ st[x]=++dfn;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]); en[x]=dfn;}inline int lca(int x,int y){ for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]])swap(x,y); return d[x]<d[y]?x:y;}inline int mergea(int x,int y){ if(!x||!y)return x+y; return e[ea[x]].b>e[ea[y]].b?x:y;}inline int mergeb(int x,int y){ if(!x||!y)return x+y; return e[eb[x]].a<e[eb[y]].a?x:y;}void build(int x,int a,int b){ if(a==b){ pos[a]=x; va[x]=vb[x]=a; return; } int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b); va[x]=mergea(va[x<<1],va[x<<1|1]); vb[x]=mergeb(vb[x<<1],vb[x<<1|1]);}void ask(int x,int a,int b){ if(C<=a&&b<=D){q[cur++]=x;return;} int mid=(a+b)>>1; if(C<=mid)ask(x<<1,a,mid); if(D>mid)ask(x<<1|1,mid+1,b);}inline void dela(int x){ va[x=pos[x]]=0; for(x>>=1;x;x>>=1)va[x]=mergea(va[x<<1],va[x<<1|1]);}inline void delb(int x){ vb[x=pos[x]]=0; for(x>>=1;x;x>>=1)vb[x]=mergeb(vb[x<<1],vb[x<<1|1]);}inline void put(const P&x){ h[++l]=x; for(int i=l;i>1&&h[i]<h[i>>1];i>>=1)swap(h[i],h[i>>1]);}inline void get(){ t=h[1],h[1]=h[l--]; for(int i=1;;){ ll tmp=h[i].first;int j=0; if((i<<1)<=l&&h[i<<1].first<tmp)tmp=h[j=i<<1].first; if((i<<1|1)<=l&&h[i<<1|1].first<tmp)j=i<<1|1; if(j)swap(h[i],h[j]),i=j;else return; }}inline void up(int x,ll d){ if(fa[x]!=x)return; fa[x]=f[x]; ans[x]=d; for(i=g[x];i;i=nxt[i])put(P(d+w[i],-i)); for(i=G[x];i;i=NXT[i])if(!vis[i])vis[i]=1,put(P(d+e[i].c,i)); C=l1[st[x]],D=r1[en[x]]; if(C<=D){ cur=0;ask(1,1,m); while(1){ for(y=i=0;i<cur;i++)y=mergea(y,va[q[i]]); if(!y)break; if(e[ea[y]].b<=en[x])break; dela(y); if(!vis[y=ea[y]])vis[y]=1,put(P(d+e[y].c,y)); } } C=l2[st[x]],D=r2[en[x]]; if(C<=D){ cur=0;ask(1,1,m); while(1){ for(y=i=0;i<cur;i++)y=mergeb(y,vb[q[i]]); if(!y)break; if(e[eb[y]].a>=st[x])break; delb(y); if(!vis[y=eb[y]])vis[y]=1,put(P(d+e[y].c,y)); } }}int F(int x){return fa[x]==x?x:fa[x]=F(fa[x]);}int main(){ fread(Buf,1,BUF,stdin);read(n),read(m),read(S); for(i=1;i<n;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z); dfs(d[1]=1),dfs2(1,1); for(i=1;i<=m;i++){ read(e[i].u),read(e[i].v),read(x),read(y),read(e[i].c); ADD(lca(x,y),i); e[i].z=d[lca(e[i].u,e[i].v)]; x=st[x],y=st[y]; if(x>y)swap(x,y); e[i].a=x,e[i].b=y; ea[i]=eb[i]=i; } if(!m)m=1; sorta(1,m); sortb(1,m); build(1,1,m); for(j=m+1,i=n;i;i--){ while(j>1&&e[ea[j-1]].a>=i)j--; l1[i]=j; } for(j=0,i=1;i<=n;i++){ while(j<m&&e[ea[j+1]].a<=i)j++; r1[i]=j; } for(j=m+1,i=n;i;i--){ while(j>1&&e[eb[j-1]].b>=i)j--; l2[i]=j; } for(j=0,i=1;i<=n;i++){ while(j<m&&e[eb[j+1]].b<=i)j++; r2[i]=j; } for(i=1;i<=n;i++)fa[i]=i; up(S,0); while(l){ get(); if(t.second>0){ z=e[t.second].z; for(x=F(e[t.second].u);d[x]>=z;x=F(x))up(x,t.first); for(x=F(e[t.second].v);d[x]>=z;x=F(x))up(x,t.first); }else up(v[-t.second],t.first); } for(i=1;i<=n;i++)write(ans[i]),*ou++=‘\n‘; fwrite(Out,1,ou-Out,stdout); return 0;}
BZOJ4699 : 树上的最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。