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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj1987Distance Statistics题解  

2014-03-31 22:03:14|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                         距离
                                            BY   LGS
题目大意:给你N个点,M条边,是颗树!!。求他们之间任意两点之间距离不超过K的路径。

题解:可以用N^2的DFS骗分,但TLE。此题是裸的树的分治,需要掌握。推荐阅读漆子超的《分治算法在树的路径问题中的应用》,先要找到树的重心,可以大幅度降低复杂度。
由于条路径,要么经过根结点,要么经过某颗子树的根结点,于是用分治,对于整颗树的所有路径《=k的答案,都在cal(每个重心,0)。对于每个根节点,若求它子树中所有符合要求的路径,就很水,直接DFS开个数组dis记录每个儿子到根节点的儿子,然后排个序,便可以O(N)的扫出答案,然而这其中其实有许多重复计算的点。因为正确的答案其实只有当两个点所在这个节点的两颗不同子树中,才能用dis解决。对于同一颗子树当中,其实他们的距离并不是这样计算的。于是我们再减去所有子树的重复计算的cal(子树节点,dis【子树节点】)这样就可以计算出cal(当前节点,0)的答案了。而整棵树是所有的cal(XX,0);重心当然是分治实现的。对于每个儿子再次调用work(子树的重心)。
而至于重心、树分治的详细求法见推荐阅读

总结:裸的树分治
代码:
  • Source Code
  • #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #define maxn 50000
    using namespace std;
    int i,j,cur,k,n,m,tot,ans,size,x,y,z,
    a[maxn],fa[maxn],dp[maxn],num[maxn],dis[maxn];
    char c;
    struct node{int end,next,s;bool use;}g[maxn*2];
    void add(int a,int b,int c)
     {
     g[tot].end=b;g[tot].next=fa[a];fa[a]=tot;
     g[tot].s=c;tot++;
     }
     
    void findroot(int w,int pre)
      {
      int i;
      dp[w]=0;
      num[w]=1;
      for (i=fa[w];i!=-1;i=g[i].next)if ((pre!=g[i].end)&&(!g[i].use))
                             {
                             findroot(g[i].end,w);
                             num[w]+=num[g[i].end];
                             dp[w]=max(dp[w],num[g[i].end]);
                             }
      dp[w]=max(dp[w],size-num[w]);if  (dp[cur]>dp[w])cur=w;
      }
    void dfs(int w,int pre)
      {int i;
      num[w]=1;a[++a[0]]=dis[w];
      for (i=fa[w];i!=-1;i=g[i].next)if ((pre!=g[i].end)&&(!g[i].use))
                              {
                              dis[g[i].end]=dis[w]+g[i].s;
                              dfs(g[i].end,w);
                              num[w]+=num[g[i].end];
                              }
      }
    int count(int w,int init)
     {
     int tem=a[0]=0;int l,r;
     dis[w]=init;
     dfs(w,0);
     sort(a+1,a+a[0]+1);
     for (l=1,r=a[0];l<r;)
        if (a[l]+a[r]<=k) {tem+=r-l;l++;}
              else r--;
     return tem;
     }
    void work(int w)
      {
      int i;
      ans+=count(w,0);
      for (i=fa[w];i!=-1;i=g[i].next)if (!g[i].use)
                                {
                                g[i^1].use=true;
                                ans-=count(g[i].end,g[i].s);
                                dp[0]=size=num[g[i].end];cur=0;
                                findroot(g[i].end,0);
                                work(cur);
                                }
      }
    int main()
    {
     scanf("%d%d",&n,&m);
     memset(fa,-1,sizeof(fa));ans=0;tot=0;
     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);
     dp[0]=size=n;cur=0;
     findroot(1,0);
     work(cur);
    printf("%d",ans);
    return 0;
    }

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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