CF266D BerDonalds（图的绝对中心）

suxxsfe · 2021-09-10 21:39:58 · 题解

https://www.cnblogs.com/suxxsfe/p/15253132.html

图的绝对中心在某节点或边上，使得所有节点到此点的距离最大值最小。

如果绝对中心在点上，那么直接对于每个 u 处理出 dis_{u,x} 最大的 x 即可。

考虑在边上的情况，若在边 (u,v,w) 上距离 u 长度为 x，则节点 i 到此点距离为 \min(dis_{u,i}+x,dis_{v,i}+(w-x))。
把这个东西关于 x 的图像画出来就是一个单峰的折线。
把 n 个点的所有折线都画出来就是这样（来自 oi-wiki）：

实线是 n 个点的折线取完 \max 的图像，然后发现所有实线的极小值的横坐标是可能的 x 的取值。
由于斜率一定，可以按照 dis_{u,i} 从大到小考虑。
设 p 是目前考虑过的所有 i 中使得 dis_{v,i} 最大的那个，此时 p 的那条折线的递减部分一定是完全暴露在外的。
因此若此时有 dis_{v,i}>dis_{v,p}，则会在 p 的递减部分产生一个新的合法最小值拐点。
那么此时 dis_{u,i}+x 和 dis_{v,p}+(w-x) 一定同时是最长路径（还没考虑到的点的拐点在 i 的后面，而交点是在 i 的拐点前面，因此图像都在 i 下面），由此计算更新答案。

#define N 206
#define M 40006
int n,m;
int val[N];
int dis[N][N],rank[N][N];
int u[M],v[M],w[M];
int main(){
    n=read();m=read();
    std::memset(dis,0x3f,sizeof dis);
    for(reg int i=1;i<=n;i++) dis[i][i]=0;
    for(reg int u,v,i=1;i<=m;i++){
        u=::u[i]=read();v=::v[i]=read();
        dis[u][v]=dis[v][u]=std::min(dis[u][v],w[i]=read());
    }
    for(reg int k=1;k<=n;k++){
        for(reg int i=1;i<=n;i++)for(reg int j=1;j<=n;j++) dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
    }
    for(reg int i=1;i<=n;i++){
        for(reg int j=1;j<=n;j++) val[j]=dis[i][j],rank[i][j]=j;
        std::sort(rank[i]+1,rank[i]+1+n,[](const int &a,const int &b){return val[a]<val[b];});
    }
    int ans=1e9;
    for(reg int i=1;i<=n;i++) ans=std::min(ans,dis[i][rank[i][n]]<<1);
    for(reg int i=1;i<=m;i++){
        int u=::u[i],v=::v[i],w=::w[i];
        for(reg int j=n-1,p=n;j;j--)if(dis[v][rank[u][j]]>dis[v][rank[u][p]]){
            ans=std::min(ans,dis[u][rank[u][j]]+dis[v][rank[u][p]]+w);
            p=j;
        }
    }
    printf("%lf\n",ans/2.0);
    return 0;
}