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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj1986Distance Queries题解  

2014-03-31 21:40:35|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                       Distance Queries
                                            BY   LGS
题目大意:给你 N个点,M条边,求任意两个点之间的距离,在树上。

题解:用DFS是K*N的效率,显然过不了,于是我学了一种新算法:离线TARJAN:用来解决LCA问题,时间效率是O(K+N)的。具体算法看推荐阅读。

总结:LCA+DFS;
代码:
  • Source Code
  • #include<cstdio>
    #define maxn 50000
    using namespace std;
    int i,j,k,n,m,tot,x,y,z,u,fa[maxn],fa2[maxn],f[maxn],dis[maxn];
    bool vist[maxn];
    char c;
    struct node{int end,next,s;}g[maxn*2],gg[maxn*2];
    int get(int w)
     {
     if (f[w]==w) return w;
      f[w]=get(f[w]);
      return f[w];
     }
    void add(int a,int b,int c)
     {
     g[++tot].end=b;g[tot].s=c;
     g[tot].next=fa[a];fa[a]=tot;
     }
    void add2(int a,int b)
     {
     gg[++tot].end=b;gg[tot].next=fa2[a];
     fa2[a]=tot;
     } 
    void LCA(int w)
     {
     int i;
     f[w]=w;vist[w]=true;
        for (i=fa[w];i;i=g[i].next)
              if (!vist[g[i].end])
                                   {
                       dis[g[i].end]=dis[w]+g[i].s;
                       LCA(g[i].end);
                       f[g[i].end]=w; 
                                   }
     for (i=fa2[w];i;i=gg[i].next)
       if (vist[gg[i].end]){
                             u=get(gg[i].end);
                            gg[i].s=dis[gg[i].end]+dis[w]-2*dis[u];
                            }
     }
    int main()
    {
     scanf("%d%d",&n,&m);
     for (i=1;i<=m;i++)
        {
        scanf("%d %d %d %c",&x,&y,&z,&c);
        add(x,y,z);
        add(y,x,z);
        }
     scanf("%d",&k);tot=0;
     for (i=1;i<=k;i++)
        {
        scanf("%d%d",&x,&y);
        add2(x,y);add2(y,x);
        }
    dis[1]=0;
    LCA(1);
    for (i=1;i<=2*k;i+=2){int ok;
                          ok=gg[i].s;
                          if (!ok) ok=gg[i+1].s;printf("%d\n",ok);
                          }
    return 0;
    }

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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