【JZOJ4884】【NOIP2016提高A组集训第12场11.10】图的半径

题目描述

mhy12345学习了树的直径，于是开始研究图的半径，具体来说，我们需要在图中选定一个地方作为中心，其中这个中心有可能在路径上。
而这个中心的选址需要能够使得所有节点达到这个中心的最短路里面最大值最小(也就是说离中心最远的结点距离尽可能小)，求出这个最大值的最小值，作为图的半径。

数据范围

N<=200，W<=100000，M<=19900
数据有梯度

分析与演绎

原题所求：选取一个实点，使得图上所有结点到这个实点的最长距离最短。
由于实点既可以取在边上，也可以取在结点上，所以可取范围很大，难以处理。
花费O(m)，原题所求转化为在一条边上选取一个实点，使得图上所有结点到这个实点的最长距离最短。
预设花费来枚举这条边上的一个实点，原题继续转化图上所有点到一个实点的最长距离最短是多少。
这就让我们感到很舒服，设这条边为(x,y)权为z，实点在与x距离为t，这个答案为ans：

a n s = m a x {m i n (d i s [i] [x] + t, d i s [i] [y] + z - t)}

我们可以利用

O(n)的时间来求得答案，但总的复杂度很高。

目前演绎的代价还是很大的，考虑继续分析。
考虑对时间复杂度影响最大的步骤，就是枚举一条边上实点的步骤。
这个复杂度为O(+∞)。
考虑交集优化：
随着t从x到y的动态过程，显然有很多实点冗余的。
对于这样的动态过程，可以考虑刻画图像来反映变化过程。

由于dis[i][x]+t是增函数，dis[i][y]+z−t是减函数，并且它们都是斜率为1或-1的一次函数。
它们要取最小值，所以它们合起来就是一个锯齿形。如下图。
这里写图片描述
n个锯齿形图像堆叠到一起。
使它们取较大值，最终图像为：

然后，我们要取这个图像上最低一点。
显然最低点都存在于两峰之间。
一个t值为峰当且仅当满足dis[i][x]+t=dis[i][y]+z−t。
这个一次方程易求解，所以n个峰值及其横坐标我们可以花O(n)代价得知。
既然最低点只存在于两峰之间，那么我们将每个峰值横坐标排序。
取两峰的编号v,v+1，这个转折点即是满足dis[v][y]+t=dis[v+1][x]+z−t的t值。
给所有转折点（即最低点）取最小值即为这条边的答案。

总的时间复杂度为O(mnlogn)。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="center.in";
const char* fout="center.out";
const int inf=0x7fffffff;
const int maxn=207,maxm=40007;
int n,m,i,j,k,l;
int f[maxn][maxn],a[maxm][3];
double ans=0,ans1,c1,c2,x;
struct node{
    int x,y;
}c[maxn];
bool cmp(node a,node b){
    return a.x>b.x || a.x==b.x && a.y<b.y;
}
void floyd(){
    int i,j,k;
    for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++){
                if (f[i][k]>2000000000 || f[k][j]>2000000000) continue;
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
}
int main(){
    freopen(fin,"r",stdin);
    freopen(fout,"w",stdout);
    scanf("%d%d",&n,&m);
    memset(f,127,sizeof(f));
    for (i=1;i<=n;i++) f[i][i]=0;
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&j,&k,&l);
        a[i][0]=j;
        a[i][1]=k;
        a[i][2]=l;
        f[j][k]=min(f[j][k],l);
        f[k][j]=min(f[k][j],l);
    }
    floyd();
    ans=inf;
    for (i=1;i<=m;i++){
        ans1=0;
        for (j=1;j<=n;j++) c[j].x=f[j][a[i][0]],c[j].y=f[j][a[i][1]];
        sort(c+1,c+n+1,cmp);
        c1=0;
        for (j=1;j<n;j++){
            c2=c[j+1].x;
            c1=max(c1,(double)c[j].y);
            if (c1<c2 && c1+a[i][2]<c2 || c1>c2 && c2+a[i][2]<c1) continue;
            ans=min(ans,(c1+a[i][2]+c2)*0.5);
        }
    }
    printf("%.2lf",ans);
    return 0;
}

启发

考虑某个值得动态变化过程，可以刻画图像。