POJ 2253 二分 + dfs / Floyd-Warshall

大緻題意

湖中分布 n 塊石頭，給出所有石頭的 xi, yi 坐标值。青蛙 Freddy 想邂逅 Fiona ，Stone #1 是 Freddy 所在的石頭, Stone #2 是 Fiona 所在的石頭。求 Freddy 必經之路上要跳過的兩塊石頭間的最短距離。輸出精度為小數點後 3 位。2<=n<=200, 0 <= xi,yi <= 1000

方法一 二分 + dfs

求最大距離的最小值，很容易想到二分法。二分上界為 Stone #1 到 Stone #2 的距離。dfs 判斷使用權值小于目前 mid 的邊時，能否由起點到達目标位置。目前搜尋的頂點無法到達目标時進行剪枝。

#include <cstdio>
#include <STDLIB.H>
#include <cmath>
#include <algorithm>
#include <iostream>
#define min(a,b)    (((a) < (b)) ? (a) : (b))
#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define abs(x)    ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define eps 1e-5
#define M_PI 3.14159265358979323846
#define MAX_W 45
#define MAX_N 200
using namespace std;
int N;
int X[MAX_N], Y[MAX_N];
double d[MAX_N][MAX_N];

double dis(int x1, int y1, int x2, int y2){
	double dx = 1.0 * (x1 - x2), dy = 1.0 * (y1 - y2);
	return sqrt(dx * dx + dy * dy);
}

bool used[MAX_N];
bool dfs(int v, double mid){
	if(v == 1) return true;
	for(int u = 0; u < N; u++){
		if(used[u] || d[v][u] > mid) continue;
		used[u] = true;
		if(dfs(u, mid)) return true;
	}
	return false;
}
int main(){
	int t = 0;
	while(~scanf("%d", &N) && N){
		for(int i = 0; i < N; i++) scanf("%d%d", X + i, Y + i);
		for(int i = 0; i < N; i++){
			for(int j = i + 1; j < N; j++){
				double v = dis(X[i], Y[i], X[j], Y[j]);
				d[i][j] = d[j][i] = v;
			}
		}
		double left = 0.0, right = d[0][1];
		while(right - left > eps){
			double mid = (left + right) / 2;
			memset(used, false, sizeof(used));
			used[0] = true;
			if(dfs(0, mid)) right = mid;
			else left = mid;
		}
		printf("Scenario #%d\n", ++t);
		printf("Frog Distance = %.3f\n\n", left);
	}
	return 0;
}
           

方法二 Floyd-Warshall

改變松弛條件，可以用最短路算法求解。因為頂點數較少，可以用 Floyd-Warshall 實作。d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))，即 i ~ j 的石頭間最大距離的最小值，用 i ~ k, k ~ j 的石頭間最大距離來更新。

#include <cstdio>
#include <STDLIB.H>
#include <cmath>
#include <map>
#include <algorithm>
#define min(a,b)    (((a) < (b)) ? (a) : (b))
#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define abs(x)    ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define eps 1e-5
#define M_PI 3.14159265358979323846
#define MAX_W 45
#define MAX_N 200
using namespace std;
int N;
int X[MAX_N], Y[MAX_N];
double d[MAX_N][MAX_N];

double dis(int x1, int y1, int x2, int y2){
	double dx = 1.0 * (x1 - x2), dy = 1.0 * (y1 - y2);
	return sqrt(dx * dx + dy * dy);
}
double floyd_wallshall(){
	for(int k = 0; k < N; k++){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
			}
		}
	}
	return d[0][1];
}
int main(){
	int t = 0;
	while(~scanf("%d", &N) && N){
		for(int i = 0; i < N; i++) scanf("%d%d", X + i, Y + i);
		for(int i = 0; i < N; i++){
			for(int j = i + 1; j < N; j++){
				double v = dis(X[i], Y[i], X[j], Y[j]);
				d[i][j] = d[j][i] = v;
			}
		}
		printf("Scenario #%d\n", ++t);
		printf("Frog Distance = %.3f\n\n", floyd_wallshall());
	}
	return 0;
}