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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ3124】【Sdoi2013】【直径】  

2014-04-08 19:13:54|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    这是noi2013快餐店的衍生产物...当然还是wshjzaa君推荐的啦...在此感谢+orz wshjzaa君。
    题目大意:1)求一棵树的直径长度。2)求所有直径都经过的边的个数。
    树的节点个数n<=2*10^5,边权<=10^9。
    第一个做法非常简单...可以直接参考快餐店那道题就可以了,关键在第二个问题。
    (按照惯例,{}所包括的都是脑洞而已...(脑洞的东西可以无视掉...))
    {
    实际上咱们知道了假如咱们DFS一棵树,就会在这个树形成深度,然后可以知道的就是直径上必然有且只有一点的深度在这棵DFS树种最低。然后这个知道了之后...咱们可以对每一个节点的最深往下链开一个数组记录有多少个后代的是这个深度,然后咱们对于是直径中心点的暴力求LCA....然后最后所有点的LCA搞一下应该就可以求出个数了...
    }
    感觉咱们需要观察出一些有用的性质...
    把观察出的一些性质写下来把~
    1)实际上咱们发现这些公共边的性质,这些边必然组成一个连通块,且一定是一条链。
    2)所有的直径之间必然有公共点,假设没有公共点,咱们把其中一条直径的一部分连向另一直径的部分必然可以得到一个不差的解。

     然后咱就直接来引用别人的几种做法了。
     第一种,神奇的DP
     第二种,神奇的DFS   
     第三种:神奇的官方题解  (这一点值得注意的是 这个SD的标解貌似默认了 直径的中心是重心了....可是这个咱还是不会证明....)(右 左边又是本蒟蒻的理解错误)(这种解法比较像咱的脑洞的解法,但咱的其实还是脑洞)
     第一种和第三种都比较神...咱就不讲了...咱比较喜欢的是比较简洁的第二种做法。就是只需要BFS的做法。(虽然说是DFS但是可能会爆)
     首先让咱们了解一下第二种做法的流程:

     1)乱搞求出一条直径。由咱们的性质1可以得出,公共边就是这条直径(链)上的一个区间。(这里突然忘记了没学DP以前咱是怎么乱搞了...所以记录一下,首先随便选个点BFS一次,求出最远点,然后从最远点BFS,再找到一个最远点,这两个点的路径就是一条直径)
     2)咱们枚举每一个点,这个点把直径分成两半,咱们BFS出从这个点开始不走直径的边能走到的最远距离,如果这个最远距离=两半中的一个,那么那一半显然不是答案,舍去。
     3)这样子删除区间,最后得到的就是答案。

      这种做法非常神,而且也非常好写。由于咱无证明不幸福...所以来尝试证明一个这个算法的正确性,实际上就是证明2)3)两步的正确性。
      首先注意到咱们有 性质2),所以每一条直径都有公共点。所以随便找条直径枚举公共点是对的。
      然后证明步骤 2)里面那样子得到的一条链为什么是直径。在2)里面实际上每次都得到了一条最远的链+一部分原直径,这里咱们说它是直径,为什么呢?假设答案是还有一条更远的>一部分原直径的话,那么 另一部分原直径+这一条更远的链>直径,这与直径的定义矛盾,所以这样子是正确的。
       所以咱们每一次如果得到了一条直径,都可以缩小范围,这样子下去枚举完所有的其他的直径,自然可以得到答案。     

       这样子咱们就可以缩小范围,然后第一次找直径是O(N)的,第二次DFS最远也是每一个点最多扫一次O(N)的,所以总的复杂度就是O(N)的。而这个实现仅仅需要BFS即可(DFS可能会爆栈)所以非常简洁的。
     
=========================================

program bzoj3124;
const maxn=200010;
type edge=record
     v,pre:longint;
     w:int64;
     end;

var n,tot,st,ed:longint;
    ans,num,len,now:int64;
    e:array[0..maxn shl 1]of edge;
    f,que,dis,last:array[0..maxn]of longint;
    d:array[0..maxn]of int64;
    ind:array[0..maxn]of boolean;

procedure addedge(u,v,w:longint);
begin
  inc(tot);e[tot].v:=v;e[tot].w:=w;
  e[tot].pre:=last[u];last[u]:=tot;
  inc(tot);e[tot].v:=u;e[tot].w:=w;
  e[tot].pre:=last[v];last[v]:=tot;
end;

function bfs(s:longint;flag:boolean):longint;
var l,r,u,tmp,id:longint;max:int64;
begin
  l:=0;r:=1;max:=0;id:=s;
  que[l]:=s;d[s]:=0;
  while l<r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>0 do
      begin
        if (not ind[e[tmp].v])and(f[u]<>e[tmp].v)then
         begin
           que[r]:=e[tmp].v;
           f[e[tmp].v]:=u;
           d[e[tmp].v]:=d[u]+e[tmp].w;
           if max<d[e[tmp].v] then
            begin
              max:=d[e[tmp].v];
              id:=e[tmp].v;
            end;
           inc(r);
         end;
        tmp:=e[tmp].pre;
      end;
     inc(l);
   end;
  if flag then exit(id)
          else exit(max);
end;

procedure init;
var i:longint;
    u,v,w,l,r:longint;
    maxlen:int64;
begin
  read(n);
  fillchar(ind,sizeof(ind),false);
  fillchar(f,sizeof(f),0);
  for i:=1 to n-1 do
   begin
     read(u,v,w);
     addedge(u,v,w);
   end;
  st:=bfs(1,true);
  f[st]:=0;
  ed:=bfs(st,true);
  fillchar(dis,sizeof(dis),0);
  len:=d[ed];
  while ed<>st do
   begin
     inc(dis[0]);
     dis[dis[0]]:=ed;
     ind[ed]:=true;
     ed:=f[ed];
   end;
  inc(dis[0]);
  dis[dis[0]]:=ed;
  ind[ed]:=true;
  l:=1;r:=dis[0];
  for i:=1 to dis[0] do
   begin
     now:=d[dis[i]];
     maxlen:=bfs(dis[i],false);
     if maxlen=now then
       if r>i then r:=i;
     if maxlen=len-now then
       if l<i then l:=i;
   end;
  writeln(len);
  if l>r then write(0)
         else write(r-l);
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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