P1399 [NOI2013] 快餐店

· · 个人记录

Roads in the Kingdom

P1399 [NOI2013] 快餐店

类似的两道题，双倍经验

题意

求基环树上的直径。

与这题类似P4381 [IOI2008] Island，只不过这道类似的题是让求最长路径，而本题是让求在最短路径上的路径，就是如果走基环的话，要走较短的那一边。

分析

直接分类讨论，考虑断掉基环上的 1 条边。

这里是为了对环上操作进行更简单的处理而分类讨论，因为基环断了，有可能原本基环上的路径又分成了别地方的子树。

这张图就很清楚。

那么答案就有 3 中可能。

分别记录下，合并答案取最小即可，记得某个环上的点挂着的树也可能是答案啊，最后要判断。

处理部分是套路，都会就不写了。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
const int N=1e5+8;
const int M=N*2;
const long long INF=1e18;
int h[N],e[M],ne[M],w[M],idx;
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int n;
bool st[N],ins[N];
int cir[N];
int cnt;
long long s[N];
int fa[N],fw[N];
void dfs_c(int u,int from){
    st[u]=ins[u]=true;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(i==(from^1)) continue;
        fa[v]=u;
        fw[v]=w[i];
        if(!st[v]){
            dfs_c(v,i);
        }
        else if(ins[v]){
            long long sum=w[i];
            // cout<<sum<<" ";
            for(int j=u;j!=v;j=fa[j]){
                cir[++cnt]=j;
                s[cnt]=sum;
                sum+=fw[j];
            }
            cir[++cnt]=v;
            s[cnt]=sum;
        }
    }
    ins[u]=false;
}
long long f[N];
long long ans1;
void dfs_d(int u,int from){
    st[u]=true;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(i==(from^1)) continue;
        if(st[v]) continue;
        dfs_d(v,i);
        ans1=max(ans1,f[u]+f[v]+w[i]);
        f[u]=max(f[u],f[v]+w[i]);
    }
}
long long l[N],r0[N],r[N],l0[N],res,ans2=INF;
int main(){
    read(n);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int u,v,w;
        read(u),read(v),read(w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=n;i++){
        if(!st[i]) dfs_c(i,-1);
    } 
    s[0]=0;
    memset(st,0,sizeof st);
    for(int i=1;i<=cnt;i++){
        st[cir[i]]=true;
    }
    for(int i=1;i<=cnt;i++){
        dfs_d(cir[i],-1);
        // cout<<cir[i]<<" ";
        // cout<<f[cir[i]]<<" ";
    }
    res=l[0]=l0[0]=-INF;
    // for(int i=1;i<=cnt;i++){
    //     cout<<cir[i]<<" ";
    // }
    //争着递推
    for(int i=1;i<=cnt;i++){
        //这里相当于s是单调递增的，我们求的是序列上[i,n]单增
        //用滑动窗口类似的东西去求
        l0[i]=max(l0[i-1],f[cir[i]]+s[i]+res);
        //树最长加到1距离
        l[i]=max(l[i-1],f[cir[i]]+s[i]),res=max(res,f[cir[i]]-s[i]);
    }
    res=r[cnt+1]=r0[cnt+1]=-INF;
    //反向s单调递减
    //原本的dis(i,j)=s[i]-s[j]如今成为了s[j]-s[i]
    for(int i=cnt;i>=1;i--){
        r0[i]=max(r0[i+1],f[cir[i]]-s[i]+res);
        //树最长加到n距离
        r[i]=max(r[i+1],f[cir[i]]+s[cnt]-s[i]),res=max(res,f[cir[i]]+s[i]);
    }
    //l+r是最长的两个点，一个在[1,i]，另一个在[i,n]
    //l0最长的两个点都在[1,i]
    //r0最长的两个点都在[i,n]
    for(int i=1;i<=cnt;i++){
        ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i])));
    }
    printf("%.1lf",max(ans1,ans2)/2.0);
    return 0;
}