注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

倍增法求LCA  

2014-04-14 10:17:41|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天看了倍增法求LCA,前几天学的tarjan貌似还是这个好用。
首先,倍增法是用来优化暴力LCA的。
暴力可以一格一格往上爬,而倍增法是2^n一格一格(n会递增)往上爬的。先用DFS构建树,并算出每个点i的深度d[i];然后如果查询x,y.假设d[x]>d[y],那么现将x调到与y严格相等的高度,无论d[x]-d[y]是怎么样的一个数,都可以用2进制来表示。
比如3:11.这样给了我们启示:我们可以先爬2格,再爬1格。6:110,先爬4格,再爬2格。
当然一开始我们要处理F[I][J]的爸爸是谁,这样才能一次次爬,j是指2的j次方距离。这个可以用递推实现F[I][J]=F[F[I][J-1]][J-1];这个很好理解的。
然后贴一下网上copy的模板,我加了注释:
  1. const int POW = 18;  
  2. void dfs(int u,int fa){  
  3.     d[u]=d[fa]+1;  
  4.     p[u][0]=fa;//爸爸  
  5.     for(int i=1;i<POW;i++) p[u][i]=p[p[u][i-1]][i-1];//递推式。 
  6.     int sz=edge[u].size();//类似邻接表
  7.     for(int i=0;i<sz;i++){  
  8.         int v=edge[u][i];  
  9.         if(v==fa) continue
  10.         dfs(v,u);  
  11.     }  
  12. }//构造树的同时实现了递推  
  13. int lca( int a, int b ){  
  14.     if( d[a] < d[b] ) a ^= b, b ^= a, a ^= b;  
  15.     if( d[a] > d[b] ){  
  16.         int del = d[a] - d[b];  
  17.         forint i = 0; i < POW; i++ ) if(del&(1<<i)) a=p[a][i];//拆分距离  
  18.     }  
  19.     if( a != b ){  
  20.         forint i = POW-1; i >= 0; i-- )//注意此处是倒着循环,留给你思考   
  21.             if( p[a][i] != p[b][i] )   
  22.                  a = p[a][i] , b = p[b][i];//第二次爬; 
  23.         a = p[a][0], b = p[b][0]; 
  24.     }  
  25.     return a;  
  26. }  


  评论这张
 
阅读(1047)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018