[51Nod2558] 选址
wenge
2020-02-06 15:44:54
# [题目链接](https://www.51nod.com/Challenge/Problem.html#problemId=2558)
题目大意：给你一个$n$个点，$m$条边的连通无向图，无自环重边，每条边连接两个点$u_i,v_i$并有一个边权$w_i$。现在要求在无向图里找到一个位置，这个位置既可以在一个点上，也可以在一条边的任意位置，要求这个位置到其他所有点的最短路的最大值最小。
首先考虑到这个位置可以在点上，也可以在边上，我们可以分开处理这两个问题。
若这个位置在一个点上，显然可以用floyd算法求这些点两两之间的最短路$f[i][j]$，然后更新答案。时间复杂度$O(n^3)$。
若这个位置在一条边上，不妨设这条边连接$u,v$两个点，长度为$a[u][v]$。我们可以先枚举$u-v$。这个时候之前用floyd算法求的最短路就可以派上用场。
我们不妨假设这个位置把边$u-v$分成了长度为$x$和$a[u][v]-x$的两部分，其中长度为$x$的部分与点$u$相接，另一部分则与点$v$相接。则一个点$p$到这个位置的最短路是
$$\min(f[p][u]+x,f[p][v]+[a][u][v]-x)$$
这样我们就可以计算当$x$为定值时的结果。我们要的答案就是
$$\max_{1\leq p \leq n}(\min(f[p][u]+x,f[p][v]+[a][u][v]-x))$$
上式的最小值。但是$x$取何值时上式取最小值呢？经过构造多组数据的验证，发现在边$u-v$一定时，上式是关于$x$的单峰函数。于是可以用三分法求解每一条边$u-v$答案的最小值。时间复杂度$O(n^3\log_{1.5}n)$。
正解代码：
```cpp
//#pragma GCC optimize(2)
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
#define PRINT(x) cout<<#x<<" = "<<x
#define br cout<<"\n"
ll n,m,loop;
double a[205][205],f[205][205],ans=1e9;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=1e9;
}
}
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
a[u][v]=a[v][u]=w;
f[u][v]=f[v][u]=w;
}
for(int i=1;i<=n;i++)f[i][i]=0;
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
for(int i=1;i<=n;i++){
double ans1=0;
for(int j=1;j<=n;j++){
ans1=max(ans1,f[j][i]);
}
ans=min(ans1,ans);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]!=0){
double l=0,r=a[i][j],mid1,mid2;
while(r-l>=1e-10){
double ansm1=0,ansm2=0;
mid1=(l+r)/2.0;
mid2=(mid1+r)/2.0;
for(int k=1;k<=n;k++){
double x=f[k][i],y=f[k][j];
ansm1=max(ansm1,min(x+mid1,y+a[i][j]-mid1));
ansm2=max(ansm2,min(x+mid2,y+a[i][j]-mid2));
}
if(ansm1<ansm2)r=mid2;
else l=mid1;
}
double ans1=0;
for(int k=1;k<=n;k++){
double x=f[k][i],y=f[k][j];
ans1=max(ans1,min(x+l,y+a[i][j]-l));
}
ans=min(ans,ans1);
}
}
}
printf("%.10lf",ans);
return 0;
}
```