bzoj3242 [Noi2013]快餐店

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

正解：基环树直径+树形$dp$。

这应该是$NOI2013$最水的一道题吧。。不过我还是写了$3$个小时，因为漏了一个情况，结果还有$95$分。。

很显然，直接求直径是错的，样例$2$就已经告诉你了。那么我们可以发现，这题其实是要求断掉环上一条边的直径，且使得这个直径最小。

我们先在环上随便找一个点作为根，然后$dfs$。先把所有树的情况处理完，这样对于每个点，$f[x]$表示$x$到它子树的最长链，用树形$dp$先搞一下就行了。

然后考虑环上怎么做。枚举断哪条边，然后我们可以记一个前缀最大值和一个后缀最大值。$v1[x]$表示环顶到$x$逆时针，$f[x]+dis(rt,x)$的最大值($rt$即为环顶)，$v2[x]$表示环顶到$x$顺时针，$f[x]+dis(rt,x)$的最大值。注意，两个$dis$是不一样的，一个是逆时针的$dis$，另一个是顺时针的。

这样，我们枚举断边，假设我们断掉的是$x->x+1$这条边，那么断这条边的直径就是$f[rt]+max(v1[x],v2[x+1])$和$v1[x]+v2[x+1]$的最大值(注意此时的$f[rt]$可能已经被别的链更新了，所以必须加上)。然后我们对于所有的最大值，取一个最小值即可。

然后这就是我开始的$95$分算法，还有一种情况没有考虑到。。

注意到上面的情况，我们可以发现它算的是环上两点距离和它们子树的最长链，但是这两点是位于断边两侧的，也就是说，断边同侧的两点同样有可能构成直径。

那么如何计算同侧的情况呢？我们设$v1[x]$为环顶到$x$逆时针，$f[x]-dis(rt,x)$的最大值，$v2[x]$为环顶到$x$顺时针，$f[x]-dis(rt,x)$的最大值。那么这时，枚举断边$i->i+1$，答案有可能由$f[x]+dis(rt,x)-v1[x-1]$和$f[x+1]+dis(rt,x+1)-v2[x+2]$的最大值构成，注意到多余部分的$dis$一加一减，正好被抵消了，所以我们是不会算错的。我们算出这两个值以及上面两个值，取一个最大值，再对所有的最大值取一个最小值，就是答案了。

 //It is made by wfj_2048~

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #define inf (1LL<<60)

 #define N (500010)

 #define il inline

 #define RG register

 #define ll long long

 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

 using namespace std;

 struct edge{ int nt,to; ll dis; }g[*N];

 int head[N],fa[N],dfn[N],low[N],st[N],n,rt,num,cnt;

 ll dis[N],f[N],d[N],v1[N],v2[N],u1[N],u2[N],ans;

 il int gi(){

     RG int x=,q=; RG char ch=getchar();

     while ((ch<'' || ch>'') && ch!='-') ch=getchar();

     if (ch=='-') q=-,ch=getchar();

     while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

     return q*x;

 }

 il void insert(RG int from,RG int to,RG ll dis){

     g[++num]=(edge){head[from],to,dis},head[from]=num; return;

 }

 il void circle(RG int rt,RG int x,RG ll len){

     RG int top=,tp=; RG ll D=len,res=inf,res1,res2;

     for (RG int i=x;i!=rt;i=fa[i]) ++tp,D+=dis[i]; top=tp;

     for (RG int i=x;i!=rt;i=fa[i]) st[tp--]=i; st[]=rt;

     for (RG int i=;i<=top;++i){

     d[i]=d[i-]+dis[st[i]];

     v1[i]=max(v1[i-],f[st[i]]+d[i]);

     u1[i]=max(u1[i-],f[st[i]]-d[i]);

     }

     for (RG int i=top;i>;--i){

     v2[i]=max(v2[i+],f[st[i]]+D-d[i]);

     u2[i]=max(u2[i+],f[st[i]]-D+d[i]);

     }

     for (RG int i=;i<top-;++i){

     res1=max(v1[i]+v2[i+],f[rt]+max(v1[i],v2[i+]));

     res2=max(f[st[i]]+d[i]+u1[i-],f[st[i+]]+D-d[i+]+u2[i+]);

     res=min(res,max(res1,res2));

     }

     res=min(res,f[rt]+v1[top]),res=min(res,f[rt]+v2[]),ans=max(ans,res); return;

 }

 il void tarjan0(RG int x,RG int p){

     fa[x]=p,dfn[x]=low[x]=++cnt; RG int v;

     for (RG int i=head[x];i;i=g[i].nt){

     v=g[i].to; if (v==p) continue;

     if (!dfn[v]){

         dis[v]=g[i].dis,tarjan0(v,x);

         low[x]=min(low[x],low[v]);

     } else low[x]=min(low[x],dfn[v]);

     }

     for (RG int i=head[x];i;i=g[i].nt){

     v=g[i].to; if (v==p) continue;

     if (fa[v]!=x && dfn[x]<dfn[v]) rt=x;

     }

     return;

 }

 il void tarjan(RG int x,RG int p){

     fa[x]=p,dfn[x]=low[x]=++cnt; RG int v;

     for (RG int i=head[x];i;i=g[i].nt){

     v=g[i].to; if (v==p) continue;

     if (!dfn[v]){

         dis[v]=g[i].dis,tarjan(v,x);

         low[x]=min(low[x],low[v]);

     } else low[x]=min(low[x],dfn[v]);

     if (dfn[x]<low[v]){

         ans=max(ans,f[x]+f[v]+g[i].dis);

         f[x]=max(f[x],f[v]+g[i].dis);

     }

     }

     for (RG int i=head[x];i;i=g[i].nt){

     v=g[i].to; if (v==p) continue;

     if (fa[v]!=x && dfn[x]<dfn[v]) circle(x,v,g[i].dis);

     }

     return;

 }

 il void work(){

     n=gi();

     for (RG int i=,u,v,w;i<=n;++i) u=gi(),v=gi(),w=gi(),insert(u,v,w),insert(v,u,w);

     tarjan0(,); for (RG int i=;i<=n;++i) dfn[i]=low[i]=fa[i]=dis[i]=;

     cnt=,tarjan(rt,); printf("%0.1Lf",0.5*(long double)ans); return;

 }

 int main(){

     File("foodshop");

     work();

     return ;

 }

巴特西