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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ3242】【Noi2013】【快餐店】  

2014-04-04 18:14:12|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    wshjzaa君最近在 做(tu) noi2013,咱是跟着他做的= =。

   这题大部分是咱自己想的...就这点觉得非常高兴= =。
   题目大意:给出一个章鱼图(这是谁命名的...)(就是N个点N条边的无向连通图)(这大概是因为N个点N条边的图是由一个环和环上的点为根的树构成的,看起来挺像章鱼0.0),求章鱼图的直径。这里的直径就是该图中所有生成树(删了一条边)的直径中最长的那一条

   首先先说说那个题意为什么会变成这个问题....
   首先咱们可以肯定的就是那个快餐店就建在直径上。因为这两个点的最短路最长,假设建在直径外面,那么到这两个点的总路程绝对比建在直径上不优,而在直径上的最优点其实就是中点....然后由于这是直径,所以答案就是直径长度的一半。所以原问题其实就是求章鱼图的直径。
    实际上一开始想的时候有种非常强烈的即视感...因为这道题让咱想到了 bzoj1023 仙人掌,那道题是求 仙人掌的直径....而这个显然就是一个仙人掌的特殊情况....即环套树(咱喜欢这么叫...)然后这道题应该可以AC了?  不行...那个的边权为1是固定的,而这个的边权可以不为1。不过这道题可以参考那个的做法来做。
   
   首先知道,这个图是由一个环为骨架构成,环上的每个点下面都接着一棵树,而它们是根。
   然后关于这个直径咱们把它分成几种可能性,第一种就是 不经过这个骨架环,只在自己的子树中。第二种就是经过环。所以咱们的方法也就是分别处理。
   首先考虑树上的如何做。(也就是说把环无视掉,只考虑环上的每一个点为根的树)。
   求树上的直径需要一次DP(貌似以前做过= =)

   咱们需要求出两个东西maxx和smaxx,maxx[i]就是以i为根的子树中i与距离i最远的节点之间的距离,然后smaxx[i]就是i与第二远的节点之间的距离。然后关于这个如何更新嘛....咱们假设dfs到一个节点u,首先把它的maxx,smaxx设为0,然后DFS儿子,每DFS一个儿子v,咱们先用儿子的maxx[v]+w[u,v]更新maxx[u],即maxx[u]=max(maxx[u],maxx[v]+w[u,v]),然后如果这个成功的话,咱们就把smaxx[u]更新为maxx[u]即可了(考虑下smaxx[u]是用来干什么的..实际上求树内部的直径,首先直径的两个端点是在叶子,然后咱们发现直径只有一个点的深度最低,咱们枚举所有点作这个点,那么实际上咱们就需要求出从这个点出发的最长和次长的路径,而且它们不能重合,不然就没必要到这个点,所以smaxx[u]在maxx[u]更新了v的情况下就直接更新原maxx[u])然后只有在maxx[u]没更新的情况下再更新smaxx[u],然后最后用所有儿子的maxx更新完之后,更新l=max(l,maxx[u]+smaxx[u])。然后这个DP就可以求出这种的最大值。

   接下来处理环,处理环先剧透下需要数据结构.... 咱用的是线段树,然后去看过ydc君的题解。传送门
   ydc君写的线段树是需要标记和修改的,但是其实这里写线段树可以不需要标记和修改的。咱们只需要类似cactus那道题一样把这条环复制一遍变成链即可。

   这样咱们就处理完树了,接下来是经过环的,经过环的咱们只需要保留 每一个点的子树中的以根为起点的最长链即可。即保留第一次DP的那个maxx[u],咱们考虑维护一个前缀和,就是把其中一条边删去然后维护一个链的前缀和,前缀和的意思就是从这个点到链最左端的距离,设之为sum[u],那么咱们要求 (sum[u]-sum[v]+maxx[u]+maxx[v]),为了方便处理,咱们用上面的环变链的方法,会发现,每一次实际上就是整个询问区间向右移动一格。然后这个就不需要区间修改单点修改了,可以直接询问了。

   听说有O(n)的算法 (0.0),应该是最后处理环要用单调队列搞吧?其实咱一开始是想用单调队列搞的,然后发现了一点.....这个的询问区间是确定不了的(但是依旧是单调递增的)....除非一开始预处理好。这个可以利用单调性扫一遍就可以了吧,但是感觉略麻烦所以就没想写了。
   实际上一开始就在写单调队列,写的头昏眼花然后发现自己这里想错了...然后又在头昏眼花中敲了一个线段树,头昏眼花地Debug了半天才弄出来。
   然后就可以A了。

   没写过恶心标记别说乃学过线段树...大概就是这种感觉吧。
   这道题咱也犯了一些错误...比如第一个..就是这个的答案可能很大...咱把初始答案设成maxlongint=10^9,而答案却有10^14....这铁定要悲剧的...然后另外一点就是...貌似数组爆了....maxn一开始就开10^5,然后大概线段树爆了吧...但是p竟然没报错233。
   然后就是一些细节。比如咱们先求出每个树的最大值,然后求环的时候需要用另一个变量求最小值即可,最后这两个取一个最大即可(这是因为咱们的环的答案是反复变化的,所以取其中的最小的,然后树每个方案实际上都存在,所以要取个最大)

   最后这题线段树没修改和标记= =结果还是比ydc君和wshjzaa君慢233....【BZOJ3242】【Noi2013】【快餐店】 - z55250825 - z55250825
    ps:这里用了编译开关调了栈的大小。如果考试的话可能就不行,所以得手写人工栈或者BFS。
============================

program noi2013foodshop; {$M 5000000} const maxn=200010; maxint=5000000000000000000; type edge=record v,pre:longint; w:int64; end; node=record wh,l,r,a,b:longint; max,smax:int64; end; var e:array[0..maxn*2]of edge; last,f,cir:array[0..maxn]of longint; maxx,smaxx,w,sum:array[0..maxn]of int64; incir:array[0..maxn]of boolean; que:array[0..maxn*2]of longint; t:array[0..1,0..maxn*4]of node; tott:array[0..1]of longint; n,tot:longint; ans,anss:int64; find: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; procedure findcir(p:longint); var tmp,top,u:longint; now:int64; begin tmp:=last[p]; while tmp<>0 do begin if f[p]<>e[tmp].v then begin if f[e[tmp].v]<>0 then begin find:=true; top:=e[tmp].v; u:=p; now:=0; while u<>top do begin incir[u]:=true; inc(cir[0]); cir[cir[0]]:=u; sum[cir[0]]:=now; now:=now+w[u]; u:=f[u]; end; incir[top]:=true; inc(cir[0]); cir[cir[0]]:=top; sum[cir[0]]:=now; now:=now+e[tmp].w; sum[cir[0]+1]:=now; exit; end; f[e[tmp].v]:=p; w[e[tmp].v]:=e[tmp].w; findcir(e[tmp].v); if find then exit; end; tmp:=e[tmp].pre; end; end; function max(a,b:int64):int64; begin if a>b then exit(a) else exit(b); end; function min(a,b:int64):int64; begin if a<b then exit(a) else exit(b); end; procedure dfs(p:longint); var tmp:longint; begin tmp:=last[p]; maxx[p]:=0; smaxx[p]:=0; while tmp<>0 do begin if (not incir[e[tmp].v])and(f[p]<>e[tmp].v) then begin f[e[tmp].v]:=p; dfs(e[tmp].v); if maxx[e[tmp].v]+e[tmp].w>=maxx[p] then begin smaxx[p]:=maxx[p]; maxx[p]:=maxx[e[tmp].v]+e[tmp].w; end else if maxx[e[tmp].v]+e[tmp].w>smaxx[p] then smaxx[p]:=maxx[e[tmp].v]+e[tmp].w; end; tmp:=e[tmp].pre; end; ans:=max(ans,maxx[p]+smaxx[p]); end; procedure maintain(kth,p:longint); begin if t[kth][t[kth][p].l].max<t[kth][t[kth][p].r].max then begin t[kth][p].max:=t[kth][t[kth][p].r].max; t[kth][p].wh:=t[kth][t[kth][p].r].wh; t[kth][p].smax:=max(t[kth][t[kth][p].r].smax,t[kth][t[kth][p].l].max); end else begin t[kth][p].max:=t[kth][t[kth][p].l].max; t[kth][p].wh:=t[kth][t[kth][p].l].wh; t[kth][p].smax:=max(t[kth][t[kth][p].l].smax,t[kth][t[kth][p].r].max); end; end; procedure build(kth,l,r:longint); var now,mid:longint; begin inc(tott[kth]);now:=tott[kth]; t[kth][now].a:=l; t[kth][now].b:=r; if l+1<r then begin mid:=(l+r)shr 1; t[kth][now].l:=tott[kth]+1; build(kth,l,mid); mid:=(l+r)shr 1; t[kth][now].r:=tott[kth]+1; build(kth,mid,r); maintain(kth,now); end else begin t[kth][now].l:=0; t[kth][now].r:=0; t[kth][now].wh:=now; t[kth][now].smax:=-1<<20; case kth of 0:t[kth][now].max:=sum[r]+maxx[cir[r]]; 1:t[kth][now].max:=maxx[cir[r]]-sum[r]; end; end; end; procedure query(kth,l,r,x:longint;var maxx,smax,wh:int64); var mid:longint; begin if (t[kth][x].a>=l)and(t[kth][x].b<=r)then begin if maxx<t[kth][x].max then begin smax:=maxx; maxx:=t[kth][x].max; wh:=t[kth][x].wh; smax:=max(smax,t[kth][x].smax); end else smax:=max(smax,t[kth][x].max); exit; end; mid:=(t[kth][x].a+t[kth][x].b)shr 1; if mid>l then query(kth,l,r,t[kth][x].l,maxx,smax,wh); if mid<r then query(kth,l,r,t[kth][x].r,maxx,smax,wh); end; procedure init; var i,j,u,v,w,l,r:longint; a:double; m1,m2,sm1,sm2,wh1,wh2:int64; begin read(n); tot:=0; fillchar(last,sizeof(last),0); for i:=1 to n do begin read(u,v,w); addedge(u,v,w); end; find:=false; fillchar(f,sizeof(f),0); fillchar(cir,sizeof(cir),0); fillchar(incir,sizeof(incir),false); fillchar(w,sizeof(w),0); f[1]:=-1; findcir(1); ans:=-1; fillchar(maxx,sizeof(maxx),0); fillchar(smaxx,sizeof(smaxx),0); for i:=1 to cir[0] do begin f[cir[i]]:=-1; dfs(cir[i]); end; for i:=cir[0]+1 to cir[0]+cir[0] do begin sum[i]:=sum[i-cir[0]]+sum[cir[0]+1]; cir[i]:=cir[i-cir[0]]; end; tott[0]:=0;tott[1]:=0; build(0,0,cir[0] shl 1); build(1,0,cir[0] shl 1); anss:=maxint; for i:=0 to cir[0] do begin m1:=-maxint;m2:=-maxint;sm1:=-maxint;sm2:=-maxint;wh1:=0;wh2:=0; query(0,i,i+cir[0],1,m1,sm1,wh1); query(1,i,i+cir[0],1,m2,sm2,wh2); if wh1<>wh2 then anss:=min(anss,m1+m2) else anss:=min(anss,max(m1+sm2,m2+sm1)); end; ans:=max(ans,anss); a:=ans/2; write(a:0:1); end; begin init; end.

  评论这张
 
阅读(131)| 评论(11)
推荐 转载

历史上的今天

评论

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

页脚

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