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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【POJ1741】【树的点分治】【Tree】  

2014-03-13 20:15:58|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    最近做的树的分治的题,据说是男人八题里面的...
    咱们找到重心然后进行分治,咱们主要考虑经过重心的路径中的个数。
   首先假设咱们的树是一颗星型的树吧,那么答案实际上就是把每一个点的距离求出来排序后,用单调性找d[i]+d[j]<=k的,咱们从小到大枚举i,由于d[i]单增,所以 对应的最大的j单减,O(N)就可以计算出来了。但是...可能不是星型的,那么,可能有两条路径在到达重心之前就已经重合了,可是这货被咱们算进去了。这个怎么办?其实也很轻松....咱们每一次DFS完一颗子树,就用刚才的算法对这个子树的所有点求一遍d[i]+d[j]<=k,然后DFS所有子树后再对整个树求一遍d[i]+d[j]<=k,用第二个的答案减去第一个的答案之和即可。当咱们递归到这棵子树的时候也是如此~
   咱的实现是给 每一个邻接表的边 加个 标记 cut,判断此条边是否已经被切断。然后每一次分治后先用普通的DFS求出信息,然后再用一个专用的DFS求出重心,然后再扫描邻接表,将与儿子相邻的每一条边及其反向边的cut都标记,然后将儿子的父亲设为该节点,再进行分治。普通的DFS里面判断是否递归到邻接点,得同时通过cut 和父亲来决定。然后这题就可以AC了。
   POJ的编译系统貌似不喜欢 P党的<<用在数组里面...CE一次,然后忘记打回车PE一次= =
===========================================

program poj1741;
const maxn=10010;
type edge=record
     v,w,pre:longint;
     cut:boolean;
     end;

var e:array[0..maxn<<1]of edge;
    last,size,f,d,sonsize:array[0..maxn]of longint;
    n,tot,limit,min,cut:longint;
    ans:int64;

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;e[tot].cut:=false;
  inc(tot);e[tot].v:=u;e[tot].w:=w;e[tot].pre:=last[v];
  last[v]:=tot;e[tot].cut:=false;
end;

procedure init;
var i,u,v,w:longint;
begin
  tot:=0;
  fillchar(last,sizeof(last),0);
  for i:=1 to n-1 do
   begin
     read(u,v,w);
     addedge(u,v,w);
   end;
end;

procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
  i:=l;j:=r;
  x:=d[(l+r)shr 1];
  repeat
    while d[i]<x do inc(i);
    while d[j]>x do dec(j);
    if i<=j then
     begin
       y:=d[i];d[i]:=d[j];d[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure dfs(p,n:longint);
var tmp,max:longint;
begin
  size[p]:=1;
  tmp:=last[p];
  max:=0;
  while tmp<>0 do
   begin
     if (not e[tmp].cut)and(f[p]<>e[tmp].v)then
      begin
        f[e[tmp].v]:=p;
        dfs(e[tmp].v,n);
        size[p]:=size[p]+size[e[tmp].v];
        if max<size[e[tmp].v] then max:=size[e[tmp].v];
      end;
     tmp:=e[tmp].pre;
   end;
  if max<n-size[p] then max:=n-size[p];
  if min>max then begin min:=max;cut:=p;end;
end;

procedure dfs2(p,len:longint;var num:longint);
var tmp:longint;
begin
  tmp:=last[p];
  inc(d[0]);
  d[d[0]]:=len;
  while tmp<>0 do
   begin
     if (not e[tmp].cut)and(e[tmp].v<>f[p])then
      begin
        f[e[tmp].v]:=p;
        dfs2(e[tmp].v,len+e[tmp].w,num);
      end;
     tmp:=e[tmp].pre;
   end;
  inc(num);
end;

procedure spilt(p:longint);
var tmp,l,r,i,v,mul,tot,w,sum,ll:longint;
begin
  tmp:=last[p];
  d[0]:=0;
  mul:=0;w:=sonsize[0];ll:=w;
  while tmp<>0 do
   begin
     if (not e[tmp].cut)and(f[p]<>e[tmp].v)then
      begin
        f[e[tmp].v]:=p;inc(w);
        l:=d[0]+1;sum:=0;
        dfs2(e[tmp].v,e[tmp].w,sum);
        sonsize[w]:=sum;
        r:=d[0];
        qsort(l,r);
        v:=r;
        for i:=l to r do
         begin
           while (v>l-1)and(d[i]+d[v]>limit) do dec(v);
           if v=l-1 then break;
           mul:=mul+(v-l+1);
         end;
      end;
     tmp:=e[tmp].pre;
   end;
  tot:=0;v:=d[0];
  qsort(1,d[0]);
  for i:=1 to d[0] do
   begin
     while (v>0)and(d[i]+d[v]>limit) do dec(v);
     if v=0 then break;
     tot:=tot+v;
   end;
  ans:=ans+(tot-mul)shr 1;
  for i:=1 to d[0] do
   if d[i]<=limit then inc(ans);
  tmp:=last[p];w:=ll;
  while tmp<>0 do
   begin
     if (not e[tmp].cut)and(f[p]<>e[tmp].v)then
      begin
        f[e[tmp].v]:=p;
        inc(w);
        min:=maxlongint;
        dfs(e[tmp].v,sonsize[w]);
        e[tmp].cut:=true;
        if tmp and 1=1 then e[tmp+1].cut:=true
                       else e[tmp-1].cut:=true;
        f[cut]:=p;
        spilt(cut);
      end;
     tmp:=e[tmp].pre;
   end;
end;

procedure main;
begin
  ans:=0;min:=maxlongint;
  dfs(1,n);
  fillchar(sonsize,sizeof(sonsize),0);
  f[cut]:=0;
  spilt(cut);
  writeln(ans);
end;

begin
  while true do
   begin
     read(n,limit);
     if (n=0)and(limit=0)then break;
     init;
     main;
   end;
end.


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

历史上的今天

评论

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

页脚

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