学步园

解题方法

方法１: nmax[i][j] 表示从i跳到j的路径的边的最大值的最小值　那么 nmax[i][j] 就可以由 max(nmax[i][k], nmax[k][j]) 更新 (1 <= k <= n) 即类似floyd

　　　　求最短路的过程

方法２: 二分这个最小值判断可行性

参考代码 - 有疑问的地方在下方留言 看到会尽快回复的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxn = 200 + 10;

double range;
int n;
bool vis[maxn];
int node[maxn][2];
int nmax[maxn][maxn];

int dis(int a, int b) {
	int x = node[a][0] - node[b][0];
	int y = node[a][1] - node[b][1];
	return x*x+y*y;
}

bool dfs(int u) {
	vis[u] = 1;
	if(u == 1) return true;
	for( int i=1; i<n; i++ ) {
		if(vis[i]) continue;
		int d = dis(u, i);
		if(d<range*range  || fabs(d-range*range)<1e-10) {
			if(dfs(i)) return true;
		}
	}
	return false;
}

bool judge(double r) {
	range = r;
	memset(vis, 0, sizeof(vis));
	if(dfs(0)) return true;
	else return false;
}

int main() {
	freopen("in", "r", stdin);
	int cnt = 1;
	while(scanf("%d", &n), n) {
		for( int i=0; i<n; i++ ) {
			scanf("%d%d", &node[i][0], &node[i][1]);
		}
		double l = 0, r = 1500; //二分法
		double res = r;
		while(fabs(l-r)>1e-5) {
			double mid = (l+r)/2;
			if(judge(mid)) {
				res = mid;
				r = mid;
			}
			else l = mid;
		}
		printf("Scenario #%d\nFrog Distance = %.3f\n\n", cnt++, res);
		continue;
		//floyd算法
		for( int i=0; i<n; i++ ) {
			for( int j=i+1; j<n; j++ ) {
				nmax[i][j] = nmax[j][i] = dis(i,j);
			}
		}
		for( int k=0; k<n; k++ ) {
			for( int i=0; i<n; i++ ) {
				for( int j=0; j<n; j++ ) {
					nmax[i][j] = min(nmax[i][j], max(nmax[i][k], nmax[k][j]));
				}
			}
		}
		printf("Scenario #%d\nFrog Distance = %.3f\n\n", cnt++, sqrt(nmax[0][1]*1.0));
	}
	return 0;
}