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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【FJOI2014】【树的点分治】【最短路径树问题】  

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

  下载LOFTER 我的照片书  |
   上午测验了一下..... 
   测验简直是丧心病狂...拿FJ的省选来做= =,当初在noip吧看了题各种想不出...然后今天刚打开题目吓傻了....
   第一题最短路径树...问题分成两个,怎么求最小编号的最短路径树和怎么求该树中所有K个节点的路径中最长的以及最长的的个数。然后第一眼直接DIJ+堆,然后每次找距离最短的扩展,有相同最短的拿编号小的扩展。然后第二个问题首先可以YY出O(N^2)的BFS暴力算法,(咱蒟蒻考场只YY出倍增LCA的O(n^2logn)的!!然后被卡了QAQ)。然后考场想起O(NlogN)可以处理路径的...不就是树的分治吗...可是....咱不会写!!
   然后暴力被卡了= =果然蒟蒻。
   然后发现构造一个五边形就可以把这个dij+堆的想法卡掉....
   然后发现应该先求最短路,然后从1开始沿着最小编号dfs.....TAT太弱了。正确姿势应该是先随便一个最短路算法乱搞然后再从1号点,每次DFS都从编号小的点到编号大的点搜索,这样就可以构造出树了。
   然后晚上突然感觉YY通了...之前理解的树的分治一直都只是停留在分治的基础上,并不知道分治之后干些什么....
   当咱们点分治之后,咱们会发现,这个问题转换成为 求只在儿子子树内部的这样的路径,和经过该分治节点的路径,然后咱们在儿子子树的递归做就可以了,现在来考虑经过该分治点的做法。
    首先咱们对于每一个儿子都进行BFS,扩展出每一个节点的深度和它到分治点的距离,然后用一个深度数组存相同深度的最大值以及这个最大值的点的个数,然后更新的时候直接先用这个数组和分治点的数组合并扫一遍(得到所有K个节点的尽量长的路径)更新答案,然后再把这个数组与分治点的数组合并,然后再处理下一个儿子。这样子就可以处理完了。显然这个复杂度只跟子树大小有关(深度最多那么深嘛...),所以复杂度就是O(NlogN)(其实咱不会算,不知道星形的那种树怎么算分治的复杂度....)
    实现方面咱给每一条边设置一个cut标记,然后每找到重心,就先DFS出每一个儿子的dep数组,然后用dep数组更新fa数组

    这题 写完了 用Cena测 8号点被卡了...然后尝试各种压常数和优化,最后发现主要的优化就是...P的初始化数组的fillchar在递归的时候不用就可以快2倍左右,最大数据未去掉fillchar 1000+ms,去掉之后400ms过了...

   UPD:一年之后回来,发现bzoj有这道题了...怒交结果发现TLE了....怀疑Bzoj数据加强,感觉可能是spfa被卡了...(具体原因不明...)

============================

const maxn=300100;
maxm=600100;

type edge=record
u,v,w,pre:longint;
cut:boolean;
end;
sp=record {树分治信息相关}
dep:array[0..maxn]of longint; {dep[i]表示深度为i的距离重心的最长距离}
num:array[0..maxn]of longint; {num[i]表示深度为i的距离为dep[i]的点的个数}
end;

var e,te:array[0..maxm]of edge;
h,st,d,pre,last,lastt,size,f,sta,que:array[0..maxn]of longint;
sonsize:array[0..maxm]of longint;
v:array[0..maxn]of boolean;
n,m,li,min,cut,tot:longint;
ans,num:int64;
fa,son:sp;

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

procedure spfa;
var ll,rr,tmp,u:longint;
begin
ll:=0;rr:=1;
fillchar(que,sizeof(que),0);
fillchar(v,sizeof(v),false);
fillchar(d,sizeof(d),1);
que[ll]:=1;v[1]:=true;d[1]:=0;
while ll<>rr do
begin
u:=que[ll];
tmp:=last[u];
while tmp<>0 do
begin
if d[e[tmp].v]>d[u]+e[tmp].w then
begin
d[e[tmp].v]:=d[u]+e[tmp].w;
if not v[e[tmp].v] then
begin
que[rr]:=e[tmp].v;
rr:=(rr+1)mod maxn;
v[e[tmp].v]:=true;
end;
end;
tmp:=e[tmp].pre;
end;
v[u]:=false;
ll:=(ll+1)mod maxn;
end;
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 (f[p]<>e[tmp].v)and(not e[tmp].cut) 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 max<min then begin min:=max;cut:=p;end;
end;


procedure dfs2(p,depth,len:longint;var maxdep,num:longint);{得到某个子树的不同节点个数的最大链长}
var tmp:longint;
begin
if son.dep[depth]=len then inc(son.num[depth]);
if son.dep[depth]<len then
begin
son.dep[depth]:=len;
son.num[depth]:=1;
end;
tmp:=last[p];
if depth<li then
while tmp<>0 do
begin
if (e[tmp].v<>f[p])and(not e[tmp].cut) then
begin
f[e[tmp].v]:=p;
dfs2(e[tmp].v,depth+1,len+e[tmp].w,maxdep,num);
end;
tmp:=e[tmp].pre;
end;
if maxdep<depth then maxdep:=depth;
inc(num);
end;

function minn(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;

procedure spilt(p:longint); {点分治}
var tmp,i,max,numm,w,ll:longint;
begin
tmp:=last[p];
fillchar(fa.dep,sizeof(fa.dep),0);
fillchar(fa.num,sizeof(fa.num),0);
w:=sonsize[0];ll:=w;
while tmp<>0 do
begin
if (not e[tmp].cut)and(e[tmp].v<>f[p]) then
begin
max:=0;numm:=0;inc(w);inc(sonsize[0]);
f[e[tmp].v]:=p;
dfs2(e[tmp].v,1,e[tmp].w,max,numm);
sonsize[w]:=numm;
for i:=1 to minn(max,li-1) do
begin
if (ans=son.dep[i]+fa.dep[li-i-1])and(fa.num[li-i-1]<>0)
and(son.num[i]<>0) then
num:=num+son.num[i]*fa.num[li-i-1];
if (ans<son.dep[i]+fa.dep[li-i-1])and(fa.num[li-i-1]<>0)
and(son.num[i]<>0) then
begin
ans:=son.dep[i]+fa.dep[li-i-1];
num:=son.num[i]*fa.num[li-i-1];
end;
end;
if (ans=son.dep[li-1])and(son.num[li-1]<>0) then
inc(num,son.num[li-1]);
if (ans<son.dep[li-1])and(son.num[li-1]<>0) then
begin
ans:=son.dep[li-1];
num:=son.num[li-1];
end;
for i:=1 to minn(max,li-1) do
begin
if fa.dep[i]=son.dep[i] then inc(fa.num[i],son.num[i]);
if fa.dep[i]<son.dep[i] then
begin
fa.dep[i]:=son.dep[i];
fa.num[i]:=son.num[i];
end;
son.dep[i]:=0;son.num[i]:=0;
end;
end;
tmp:=e[tmp].pre;
end;
tmp:=last[p];w:=ll;
while tmp<>0 do
begin
if (not e[tmp].cut)and(e[tmp].v<>f[p]) then
begin
e[tmp].cut:=true;
if tmp and 1=1 then e[tmp+1].cut:=true
else e[tmp-1].cut:=true;
inc(w);
if sonsize[w]>=li then
begin
min:=maxlongint;
f[e[tmp].v]:=p;
dfs(e[tmp].v,sonsize[w]);
f[cut]:=p;
spilt(cut);
end;
end;
tmp:=e[tmp].pre;
end;
end;

procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
if l>r then exit;
i:=l;j:=r;
x:=te[sta[(l+r)shr 1]].v;
repeat
while te[sta[i]].v<x do inc(i);
while te[sta[j]].v>x do dec(j);
if i<=j then
begin
y:=sta[i];sta[i]:=sta[j];sta[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 dfs3(p:longint); {构造出最短路径树}
var l,r,tmp,i:longint;
begin
v[p]:=true;
l:=sta[0]+1;
tmp:=lastt[p];
while tmp<>0 do
begin
if (not v[te[tmp].v])and(d[te[tmp].v]=d[p]+te[tmp].w) then
begin
inc(sta[0]);sta[sta[0]]:=tmp;
end;
tmp:=te[tmp].pre;
end;
r:=sta[0];
qsort(l,r);
for i:=l to r do
if not v[te[sta[i]].v] then
begin
addedge(p,te[sta[i]].v,te[sta[i]].w);
dfs3(te[sta[i]].v);
end;
end;

procedure init;
var i,u,vv,w:longint;
begin
read(n,m,li);
fillchar(last,sizeof(last),0);
tot:=0;
for i:=1 to m do
begin
read(u,vv,w);
addedge(u,vv,w);
end;
spfa;
tot:=0;
te:=e;
lastt:=last;
fillchar(last,sizeof(last),0);
fillchar(sta,sizeof(sta),0);
fillchar(v,sizeof(v),false);
dfs3(1);
fillchar(v,sizeof(v),false);
fillchar(size,sizeof(size),0);
fillchar(sonsize,sizeof(sonsize),0);
min:=maxlongint;
dfs(1,n);
ans:=0;num:=0;
f[cut]:=0;
spilt(cut);
writeln(ans,' ',num);
end;

begin
assign(input,'short.in');reset(input);
assign(output,'short.out');rewrite(output);
init;
close(input);
close(output);
end.


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

历史上的今天

评论

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

页脚

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