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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj1985Cow Marathon题解  

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

  下载LOFTER 我的照片书  |
                                                             奶牛马拉松
                                          BY   LGS
题目大意:给你N个点,M条边,注意(题目没说清楚是不是树,看了别人题解才知道一定是树),否则很难做了。找到树中两个点的最远距离。

题解:DP可以过的,一开始先BFS建树,然后DP1[i]表示到第i个结点的最长距离,DP2[i]表示到第i个结点的第二长距离,答案便在1-n的DP1[I]+DP2[I];网上有更方便的做法,这是求树的直径。而对于树的直径,可以直接从任意一点DFS出发到最远的一点记录下来。再从最远的一点再DFS到最远的一点,中间的路径长度即为所求。

总结:DFS+树
代码:
  • Source Code
  • #include<cstdio>
    #include<cstring>
    #define maxn 50000
    using namespace std;
    int ans,i,j,k,tot,n,m,x,y,z,t,flag,fa[maxn];
    bool b[maxn];
    struct node{int end,s,next;}g[maxn*2];
    char c;
    void add(int a,int b,int c)
     {
     g[++tot].end=b;g[tot].next=fa[a];
     g[tot].s=c;
     fa[a]=tot;
     }
    void dfs(int w,int t)
     {
     int i;
     b[w]=true;if (t>ans){ans=t;flag=w;}
     for (i=fa[w];i;i=g[i].next)
           if (!b[g[i].end]) 
              dfs(g[i].end,t+g[i].s);
     }
    int main()
    {
     scanf("%d%d",&n,&m);tot=0; 
     for (i=1;i<=m;i++)
           {
           scanf("%d%d%d",&x,&y,&z);
           for (j=1;j<=3;j++) c=getchar();
           add(x,y,z);add(y,x,z);
           }
    dfs(1,0);
    memset(b,false,sizeof(b));ans=0;
    dfs(flag,0);
    printf("%d\n",ans);
    return 0;
    }

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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