BZOJ1509 NOI2003 Hookey - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ3289 Mato文件管理
NOI2014 Day1 废话题解

BZOJ1509 NOI2003 Hookey

Hoblovski posted @ 2014年7月20日 23:00 in Solutions with tags BZOJ DP 啪啪啪 , 923 阅读
题意 给定带权无根树T.找到T中三个顶点A,B,C,满足d(A,B)<=d(B,C).
最大化 d(B,A)+d(A,C).
 
Tag DP,啪啪啪
 
没能好好学集训的我只好无可奈何来做NOI题.
挺像树的直径对吧.最终这个和直径没什么太大关系.
我们可以通过"直径有多条"来否定很多用直径乱搞的算法.
最终答案不一定是一条链啊,可能是一个三岔路啊我又犯SB了集训完上YY出来一个错误算法兴奋直到WA.....
之后三岔路长度分别是a,b,c,a<=b<=c,显然这个三岔路提供的答案就是a+2b+c.
...我们可以枚举这个三岔路的中间点来DP.中间点就是从这个点开始BFS后三个点处于不同子树,这三个点可以是中间点,于是问题转化为
对于每个点找出树中距离他最远第二远第三元的距离,要求这个点是他们的中心点.
BFS建成有根树.
之后就是分类讨论
1.最远第二远第三元的距离在子树内.裸上树DP
于是我们记 d[u][1]表示u到u子树内最近,d[u][2]第二近..
2.这个距离在子树外.这个点通向子树外只有一条路所以我们就考虑到子树外的最远距离.定义u到u子树外最远距离为od[u],记u的父亲是v.
od[u]=max{od[v],无条件
   d[v][2],v只有一个儿子r,r=u满足d[r][1]+w(r,v)=d[v][1].
   d[v][1],否则
  }+w(u,v);
希望不要再犯SB了
 
{$INLINE ON}
program bzoj1509_1;
 
const size=3;
 
type tnode=record
        n,w,next:longint;
     end;
     inta=array[1..size] of int64;
 
const maxn=200017;
 
var g,q,p,pe,son:array[0..maxn] of longint;
    v,flag:array[0..maxn] of boolean;
    d:array[0..maxn] of inta;
    od:array[0..maxn] of int64;
    mem:array[0..maxn*2] of tnode;
    n,m,memsize,frt,rer:longint;
 
function max(i,j:int64):int64; inline; begin if i>j then exit(i) else exit(j); end;
 
procedure insnbs(u,v,iw:longint); inline;
begin
inc(memsize); with mem[memsize] do begin n:=v; w:=iw; next:=g[u]; end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin n:=u; w:=iw; next:=g[v]; end; g[v]:=memsize;
end;
 
procedure insert(var s:inta;v:int64); inline;
var i:longint;
begin
for i:=1 to size do if v>s[i] then begin
        if i<size then move(s[i],s[i+1],(size-i)<<3); s[i]:=v; break;
end;
end;
 
function dp(u:longint):int64;
var head,tail,t1,i,j:longint;
    k:int64;
begin
fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),0); frt:=0; rer:=1; q[rer]:=u; v[u]:=true;
while frt<rer do begin inc(frt); head:=q[frt];
        t1:=g[head]; while t1<>0 do begin tail:=mem[t1].n;
                if not v[tail] then begin
                        inc(rer); q[rer]:=tail; v[tail]:=true; p[tail]:=head; pe[tail]:=t1;
                end; t1:=mem[t1].next;
        end;
end; for j:=rer downto 2 do begin i:=q[j]; k:=d[i][1]+mem[pe[i]].w;
        if k>d[p[i]][1] then son[p[i]]:=i; insert(d[p[i]],k);
end; for i:=1 to n do flag[son[i]]:=true; fillchar(od,sizeof(od),0); for j:=2 to rer do begin
        i:=q[j]; od[i]:=max(od[p[i]],d[p[i]][1+byte(flag[i])])+mem[pe[i]].w;
end; for i:=1 to n do insert(d[i],od[i]); dp:=0; for i:=1 to n do dp:=max(dp,d[i][1]+d[i][2]<<1+d[i][3]);
end;
 
procedure init;
var i,j,u,v,w:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1; fillchar(flag,sizeof(flag),0);
readln(n,m); for i:=1 to m do begin readln(u,v,w); insnbs(u,v,w); end;
end;
 
begin
init;
writeln(dp(1));
end.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter