2016-09-08

Codeforces 266D BerDonalds【图绝对中心】

题目链接：

http://codeforces.com/contest/266/problem/D

题意：

求图的绝对中心，即在边上或者顶点中选一个点$X$，使得该点到图中顶点的最远距离$f(X)$最小。

分析：

=== 我是搬运工===

首先$floyd$求出任意两点之间的最短路。
其次，根据题意，对于某一点$X，设其在线段$u-v$上，与点$u$的距离为$x$，对于任意点$w$，我们有f(X)=max\ (min\ (d[u][w]+x, d[v][w]+L_{u,v}-x\ )\ )$。
下面来分析$f(X)$的性质，对于固定的线段$u-v$，我们可以画出$f(X)关于x$的函数图像，为方便比较，把$w$们放在一个坐标系中，由于我们要求的是到其他点的最大值，所以对于某个$x$，只要保留该$x$对应的最大的$f(x)$值即可，也就是函数图像中最上面的点，如下图实线所示。
Alt text
$f(X)$的最小值就是实线中的最低点，观察图可知，这个最小值必然在交叉点上，即$L_1，L_2，L_3…$。
根据函数图像，存在交叉点的前提是$d[u][w_j] > d[u][w_k] 并且 d[v][w_j] < d[v][w_k]$，且有$d[u][w_j] + L_{u,v} - x = d[v][w_k] + x$，而此时的$f(X)= \frac{d[u][w_j] + L_{u,v} - x + d[v][w_k]+ x}{2} = \frac{d[u][w_j] + L_{u,v} + d[v][w_k]}{2}$
这样我们枚举每一条边，然后对于$d[u][w]$从大到小排个序，扫一遍，按照上述式子答案就出来了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int, int>p;
const int maxn = 2e2 + 5, oo = 0x3f3f3f3f ;
int dist[maxn][maxn];
struct EDGE{
	int from, to, val;
}edge[maxn * maxn];
p node[maxn];
int tot;
int main (void)
{
	int n, m;scanf("%d%d", &n, &m);
	int a, b, w; 
	tot = 0;
	memset(dist, 0x3f, sizeof(dist));
	for(int i = 0; i < m; i++){
		scanf("%d%d%d", &a, &b, &w);
		a--;b--;
		dist[a][b] = dist[b][a] = w;
		edge[tot++] = (EDGE){a, b, w};
	}
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j)	dist[i][j] = 0;
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	int ans = oo;
	int tmp;
	for(int i = 0; i < tot; i++){
		int u = edge[i].from, v = edge[i].to;
		for(int j = 0; j < n; j++){
			node[j] = p(dist[j][u], dist[j][v]);
		}
		tmp = n - 1;
		sort(node, node + n);
		ans = min(ans, node[n - 1].first * 2);
		for(int j = n - 2; j >= 0; j--){
			if(node[j].second > node[tmp].second){
				ans = min(ans, node[tmp].second + node[j].first + edge[i].val);
				tmp = j;
			}
		}	
		ans = min(ans, node[tmp].second * 2);	
	}
	printf("%.10f\n", (double)ans / 2.0);
	return 0;
}