首页 > 代码库 > 3242: [Noi2013]快餐店 - BZOJ

3242: [Noi2013]快餐店 - BZOJ

Description

小T打算在城市C开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小T希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市C的N 个建筑中,这N 个建筑通过恰好N 条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小T的快餐店可以开设在任一建筑中,也可以开设在任意一条道路的某个位置上(该位置与道路两端的建筑的距离不一定是整数)。 现给定城市C的地图(道路分布及其长度),请找出最佳的快餐店选址,输出其与最远的顾客之间的距离。



Input

第一行包含一个整数N,表示城市C中的建筑和道路数目。
接下来N行,每行3个整数,Ai,Bi,Li(1≤i≤N;Li>0),表示一条道路连接了建筑Ai与Bi,其长度为Li 。

Output

仅包含一个实数,四舍五入保留恰好一位小数,表示最佳快餐店选址距离最远用户的距离。
注意:你的结果必须恰好有一位小数,小数位数不正确不得分。
Sample Input
1 2 1
1 4 2
1 3 2
2 4 1
Sample Output
2.0
HINT



数据范围

对于 10%的数据,N<=80,Li=1;

对于 30%的数据,N<=600,Li<=100;

对于 60% 的数据,N<=2000,Li<=10^9;

对于 100% 的数据,N<=10^5,Li<=10^9

 

首先把环求出来,然后枚举删掉环上某条边,再算出现在的直径,然后取个min

我们先求出不经过环的最长链,然后每次都只用做经过环的最长链了

删掉一条边我们得到了一条链,每个点有两个属性,一个是d[i],表示不走链最长的距离,一个是S[i],表示从1走环上的边到i的距离

我们要求的是max{S[j]-S[i]+d[i]+d[j]},所以我们维护max{S[i]+d[i]}和max{d[i]-S[i]},但是两个点不能是同一个点所以再维护一下次小值和最大值的编号,用线段树

 

  1 const  2     maxn=100100;  3     inf=10000000000000000000000000000;  4 type  5     node=record  6         max:array[0..1]of double;  7         id,l,r,lc,rc:longint;  8     end;  9 var 10     first,huan,fa:array[0..maxn]of longint; 11     d:array[0..maxn,0..1]of double; 12     next,last:array[0..maxn*2]of longint; 13     l,len,a:array[0..maxn*2]of double; 14     vis:array[0..maxn]of boolean; 15     f:array[0..maxn*4]of node; 16     n,tot,cnt,num,root1,root2:longint; 17     ans,ans1,s:double; 18   19 function max(x,y:double):double; 20 begin 21     if x>y then exit(x); 22     exit(y); 23 end; 24   25 function min(x,y:double):double; 26 begin 27     if x<y then exit(x); 28     exit(y); 29 end; 30   31 procedure insert(x,y:longint;z:double); 32 begin 33     inc(tot); 34     last[tot]:=y; 35     next[tot]:=first[x]; 36     first[x]:=tot; 37     l[tot]:=z; 38 end; 39   40 procedure dfs1(x:longint); 41 var 42     i,j:longint; 43 begin 44     i:=first[x]; 45     vis[x]:=true; 46     while i<>0 do 47         begin 48             if cnt>0 then exit; 49             if (last[i]<>fa[x]) and vis[last[i]] then 50             begin 51                 j:=x; 52                 len[last[i]]:=l[i]; 53                 while j<>fa[last[i]] do 54                     begin 55                         inc(cnt); 56                         huan[cnt]:=j; 57                         j:=fa[j]; 58                     end; 59             end; 60             if not vis[last[i]] then 61             begin 62                 fa[last[i]]:=x; 63                 len[last[i]]:=l[i]; 64                 dfs1(last[i]); 65             end; 66             i:=next[i]; 67         end; 68 end; 69   70 procedure dfs2(x:longint); 71 var 72     i:longint; 73 begin 74     vis[x]:=true; 75     i:=first[x]; 76     while i<>0 do 77         begin 78             if not vis[last[i]] then 79             begin 80                 dfs2(last[i]); 81                 if d[last[i],0]+l[i]>d[x,0] then 82                     begin 83                         d[x,1]:=d[x,0]; 84                         d[x,0]:=d[last[i],0]+l[i]; 85                     end 86                 else 87                     if d[last[i],0]+l[i]>d[x,1] then d[x,1]:=d[last[i],0]+l[i]; 88             end; 89             i:=next[i]; 90         end; 91     if ans<d[x,0]+d[x,1] then ans:=d[x,0]+d[x,1]; 92 end; 93   94 procedure new(x:longint); 95 begin 96     f[x].max:=f[f[x].lc].max; 97     f[x].id:=f[f[x].lc].id; 98     if f[f[x].rc].max[0]>f[x].max[0] then 99         begin100             f[x].max[1]:=f[x].max[0];101             f[x].max[0]:=f[f[x].rc].max[0];102             f[x].id:=f[f[x].rc].id;103         end104     else105         if f[f[x].rc].max[0]>f[x].max[1] then f[x].max[1]:=f[f[x].rc].max[0];106     if f[f[x].rc].max[1]>f[x].max[1] then f[x].max[1]:=f[f[x].rc].max[1];107 end;108  109 procedure build(l,r:longint);110 var111     now,mid:longint;112 begin113     inc(num);now:=num;114     f[now].l:=l;f[now].r:=r;115     if l=r then116     begin117         f[now].max[0]:=a[l];118         f[now].max[1]:=-inf;119         f[now].id:=l;120         exit;121     end;122     mid:=(l+r)>>1;123     f[now].lc:=num+1;build(l,mid);124     f[now].rc:=num+1;build(mid+1,r);125     new(now);126 end;127  128 procedure add(now,x:longint;y:double);129 var130     mid:longint;131 begin132     if f[now].l=f[now].r then133     begin134         f[now].max[0]:=y;135         exit;136     end;137     mid:=(f[now].l+f[now].r)>>1;138     if x<=mid then139         add(f[now].lc,x,y)140     else141         add(f[now].rc,x,y);142     new(now);143 end;144  145 procedure main;146 var147     i,x,y:longint;148     z:double;149 begin150     read(n);151     for i:=1 to n do152         begin153             read(x,y,z);154             insert(x,y,z);155             insert(y,x,z);156         end;157     dfs1(1);158     for i:=1 to n do vis[i]:=false;159     for i:=1 to cnt do vis[huan[i]]:=true;160     for i:=1 to cnt do dfs2(huan[i]);161     z:=0;162     for i:=1 to cnt do163         begin164             a[i]:=z+d[huan[i],0];165             z:=z+len[huan[i]];166         end;167     root1:=num+1;build(1,cnt);168     z:=0;169     for i:=1 to cnt do170         begin171             a[i]:=d[huan[i],0]-z;172             z:=z+len[huan[i]];173         end;174     root2:=num+1;build(1,cnt);175     ans1:=inf;176     for i:=1 to cnt do177         begin178             if f[root1].id<>f[root2].id then179                 ans1:=min(ans1,f[root1].max[0]+f[root2].max[0])180             else181                 ans1:=min(ans1,max(f[root1].max[1]+f[root2].max[0],f[root1].max[0]+f[root2].max[1]));182             s:=s+len[huan[i]];183             add(root1,i,z-len[huan[i]]+d[huan[i],0]+s);184             add(root2,i,d[huan[i],0]-z+len[huan[i]]-s);185         end;186     ans:=max(ans,ans1);187     writeln(ans/2:0:1);188 end;189  190 begin191     main;192 end.
View Code