题解 51nod2558 选址

题解 51nod2558 选址

题面

51nod

解析

本人用的是官方题解的做法(就解题报告里那个).

首先用 ( exttt{floyd}) 求出两个点之间的最短路.

考虑枚举答案所在的边,设当前枚举的是 ((x,y)).

我们把所有点(包括 (x,y))按照离 (x) 的距离从大到小排序,

设排完序后的数组为 (c),枚举 (i),令最终选的点到 (c_idots c_n) 这些点都经过 (x),

显然最长的一条路是 (x o c_i).

然后让 (c_1dots c_{i-1}) 这些点都经过 (y),维护路径长度的最大值.

这样我们就找出了一条最长路,而最长路的中点即为答案点所在.

但是要注意一个地方:这个中点可能不在枚举的这条边上.

因此排除掉这种情况即可.

code

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;

inline int read(){
	int sum=0,f=1;char c=getchar();
	while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}

const int N=205;
const int INF=0x3f3f3f3f;
struct edge{int x,y,w;}a[N*N];
int n,m,c[N];ll d[N][N],f[N];

inline bool cmp(int a,int b){
	return f[a]>f[b];
}

int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) d[i][j]=INF;
	for(int i=1;i<=n;i++) d[i][i]=0;
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),w=read();
		a[i]=(edge){x,y,w};
		d[y][x]=d[x][y]=min(d[x][y],1ll*w);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	ll ans=INF;
	for(int i=1;i<=m;i++){
		int x=a[i].x,y=a[i].y;
		ll sum=0;int tot=n;
		for(int j=1;j<=n;j++) c[j]=j,f[j]=d[x][j];
		sort(c+1,c+tot+1,cmp);
		for(int j=1;j<=tot;j++){
			ll tem=d[x][c[j]]+a[i].w+sum;
			if(tem>=d[x][c[j]]<<1&&tem<=(d[x][c[j]]+a[i].w)<<1) ans=min(ans,tem);
			sum=max(sum,d[y][c[j]]);
		}
	}
	printf("%lf
",1.0*ans/2);
	return 0;
}