首页 > 代码库 > 「Nescafé26」 Freda的传呼机 【树上倍增+图论】
「Nescafé26」 Freda的传呼机 【树上倍增+图论】
题目:
为了随时与rainbow快速交流,Freda制造了两部传呼机。Freda和rainbow所在的地方有N座房屋、M条双向光缆。每条光缆连接两座房屋,传呼机发出的信号只能沿着光缆传递,并且传呼机的信号从光缆的其中一端传递到另一端需要花费t单位时间。现在Freda要进行Q次试验,每次选取两座房屋,并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。Freda和rainbow简直弱爆了有木有T_T,请你帮帮他们吧……
N座房屋通过光缆一定是连通的,并且这M条光缆有以下三类连接情况:
A:光缆不形成环,也就是光缆仅有N-1条。
B:光缆只形成一个环,也就是光缆仅有N条。
C:每条光缆仅在一个环中
颂芬数据占10%,2<=N<=1000,N-1<=M<=1200。
A类数据占30%,M=N-1。
B类数据占50%,M=N。
C类数据占10%,M>N。
对于100%的数据,2<=N<=10000,N-1<=M<=12000,Q=10000,1<=x,y<=N,1<=t<32768。
分析:
(对于直接想要AC的人,可以直接忽略此部分)
可以看到:对于10%的数据,可以简简单单跑一个SPFA,(但一定要注意细节,严格按照模板来),下面给出10分的代码(通往AC的路是循序渐进的):
剩下的能跑出树上倍增的,相信离成功也不远了。仔细看看题目中红色的字体,会发现实际上所有的环只可能有公共顶点,不可能有公共边,这样画出来就很像一个仙人掌(其实名称都不重要),那么我们该如何处理这样的一个个环呢?其实可以想到,我们以每一个公共顶点为树根,可以把多个环转化成一棵树,其中树枝长就是环中每个点到顶点的最短距离,但一定要分别记录每个点从两边到环顶的距离 l[i] 和 r[i],因为转换成一棵树后,从树上看来似乎是每两个点之间的路径必过顶点,但实际上在环中两个点完全可以不通过顶点而相互到达,因此两个点若在一个环中(这里实现的时候用一个数组分别记录每个点所在的环的编号和环顶),就有:
dis[x][y]= min( l[x]+r[y] , l[y]+r[x] , abs(r[x]-r[y]) );//一左一右到环顶,一右一左到环顶,和不通过环顶
然后至于树上倍增,我们用fa[x][i]表示从x这个节点往上2^i步能到的节点,用dis[x][i]表示从x这个节点到fa[x][i]这个祖先的距离;
就有初始化(递推):
fa[x][i]=fa[fa[x][i-1]][i-1];//从上一个位置再走一步
dis[x][i]=dis[fa[x][i-1]][i-1]+dis[x][i-1];//走半截再走半截
于是此题就可以AC了:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 const int maxn=121000; 8 struct point1 9 { 10 int to,nxt,w; 11 }edge[maxn<<1]; 12 struct point2 13 { 14 int to,nxt,w; 15 }edge2[maxn<<1]; 16 int n,m,Q,a,b,ww,ss=0,ttt=0,n_cir=0; 17 int lop[maxn][4];//详见62~65行 18 int e[maxn][4],pre[maxn][3],bin[20],dfn[maxn],dep[maxn],head1[maxn],head2[maxn]; 19 /*pre[i][0/1],0为i前一个是谁,1为i前一条边长*/ 20 int dis[maxn][20],fa[maxn][20]; 21 22 void init() 23 { 24 bin[0]=1; 25 for(int i=1;i<=18;i++) 26 bin[i]=bin[i-1]<<1; 27 } 28 29 int cnt=0; 30 void add(int u,int v,int wei) 31 { 32 edge[cnt].to=v; 33 edge[cnt].nxt=head1[u]; 34 edge[cnt].w=wei; 35 head1[u]=cnt++; 36 } 37 38 int ct=0; 39 void ins(int u,int v,int wei) 40 { 41 edge2[ct].to=v; 42 edge2[ct].nxt=head2[u]; 43 edge2[ct].w=wei; 44 head2[u]=ct++; 45 46 } 47 48 void dfs(int x,int y,int fa) 49 { 50 ttt++; 51 dfn[x]=ttt; 52 for(int i=head1[x];~i;i=edge[i].nxt) 53 { 54 int v=edge[i].to; 55 if(v==fa && i==(y^1)) continue; 56 if(dfn[v]!=0 && dfn[v]<dfn[x])//找到一个环 57 { 58 int len=edge[i].w; 59 n_cir++; 60 for(int j=ss;pre[j][0]!=v;j--) 61 len+=pre[j][1]; 62 lop[x][0]=n_cir;//环的编号 63 lop[x][1]=v;//环的顶点 64 lop[x][2]=edge[i].w;//从一边到顶点的距离 65 lop[x][3]=len-lop[x][2];//从另一边 66 ins(v,x,min(lop[x][2],lop[x][3]));//正反建图 67 ins(x,v,min(lop[x][2],lop[x][3]));//按最短路径重新建图 68 for(int j=ss-1;pre[j][0]!=v;j--) 69 { 70 int z=pre[j][0]; 71 lop[z][0]=n_cir; 72 lop[z][1]=v; 73 lop[z][2]=lop[pre[j+1][0]][2]+pre[j+1][1]; 74 lop[z][3]=len-lop[z][2]; 75 ins(v,z,min(lop[z][2],lop[z][3])); 76 ins(z,v,min(lop[z][2],lop[z][3])); 77 } 78 } 79 if(dfn[v]) 80 continue; 81 pre[++ss][0]=v; 82 pre[ss][1]=edge[i].w; 83 dfs(v,i,x); 84 } 85 ss--; 86 } 87 88 void dfss(int x) 89 { 90 for(int i=1;i<=18;i++) 91 { 92 if(dep[x]<bin[i]) break; 93 fa[x][i]=fa[fa[x][i-1]][i-1]; 94 dis[x][i]=dis[fa[x][i-1]][i-1]+dis[x][i-1]; 95 } 96 for(int i=head2[x];~i;i=edge2[i].nxt) 97 { 98 if(edge2[i].to!=fa[x][0]) 99 { 100 int v=edge2[i].to; 101 fa[v][0]=x; 102 dep[v]=dep[x]+1;//深度在待会lca要用 103 dis[v][0]=edge2[i].w; 104 dfss(v); 105 } 106 } 107 } 108 109 int lca(int x,int y) 110 { 111 int sum=0; 112 if(dep[x]<dep[y]) swap(x,y); 113 int t=dep[x]-dep[y]; 114 for(int i=0;i<=18;i++) 115 if(t&bin[i])//y在x下面,t的二进制在i那一位上有1 (保证要用2^i凑齐t) 116 { 117 sum+=dis[x][i]; 118 x=fa[x][i]; 119 } 120 for(int i=18;i>=0;i--) 121 { 122 if(fa[x][i]!=fa[y][i]) 123 { 124 sum+=dis[x][i]+dis[y][i]; 125 x=fa[x][i]; 126 y=fa[y][i]; 127 } 128 } 129 if(x==y) return sum; 130 if(lop[x][0]==lop[y][0] && lop[x][0]!=0) 131 sum+=min(min(lop[x][2]+lop[y][3],lop[y][2]+lop[x][3]),abs(lop[x][2]-lop[y][2])); 132 else 133 sum+=dis[x][0]+dis[y][0]; 134 return sum; 135 } 136 137 int main() 138 { 139 memset(head1,-1,sizeof(head1)); 140 memset(head2,-1,sizeof(head2)); 141 init(); 142 cin>>n>>m>>Q; 143 for(int i=1;i<=m;i++) 144 { 145 cin>>a>>b>>ww; 146 add(a,b,ww); 147 add(b,a,ww); 148 e[i][1]=a; 149 e[i][2]=b; 150 e[i][3]=ww; 151 } 152 ss=1; 153 pre[1][0]=1; 154 pre[1][1]=0; 155 dfs(1,-1,0);//找环,并计算出每个点到环顶的最短路 156 for(int i=1;i<=m;i++) 157 { 158 int aa=e[i][1]; 159 int bb=e[i][2]; 160 int cc=e[i][3]; 161 if( (lop[aa][0]!=lop[bb][0] || !lop[aa][0] || !lop[bb][0]) && lop[aa][1]!=bb && lop[bb][1]!=aa) 162 { 163 ins(aa,bb,cc); 164 ins(bb,aa,cc); 165 } 166 } 167 dfss(1);//倍增处理 168 while(Q--) 169 { 170 cin>>a>>b; 171 cout<<lca(a,b)<<endl; 172 } 173 return 0; 174 }
「Nescafé26」 Freda的传呼机 【树上倍增+图论】