【POJ - 2253】Frogger（floyd，或 部分瓶颈生成树的最大边）

题干：

湖中有n块石头，编号从1到n，有两只青蛙，Bob在1号石头上，Alice在2号石头上，Bob想去看望Alice，但由于水很脏，他想避免游泳，于是跳着去找她。但是Alice的石头超出了他的跳跃范围。因此，Bob使用其他石头作为中间站，通过一系列的小跳跃到达她。两块石头之间的青蛙距离被定义为两块石头之间所有可能路径上的最小必要跳跃距离，某条路径的必要跳跃距离即这条路径中单次跳跃的最远跳跃距离。你的工作是计算Alice和Bob石头之间的青蛙距离。

Input

多实例输入 
先输入一个整数n表示石头数量，当n等于0时结束。
接下来2-n+1行依次给出编号为1到n的石头的坐标xi , yi。
2 <= n <= 200 
0 <= xi , yi <= 1000

Output

先输出"Scenario #x"， x代表样例序号。
接下来一行输出"Frog Distance = y"， y代表你得到的答案。 
每个样例后输出一个空行。
（ps：wa有可能是精度问题，g++不对可以用c++尝试，都不对就是代码问题）

Sample Input

2
0 0
3 4

3
17 4
19 4
18 5

0

Sample Output

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414

题目大意：

1为起点，2为终点，那么1~2的所有路径，每条路径的最大边构成一个边集E，让你求E中的最小值。

解题报告：

  这题可以直接跑MST，然后当1~2已经连通的时候就break就行了，这时候得到的就是答案。

  法二跑个floyd稍微修改一下也行。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e2 + 5;
double dis[MAX][MAX];
int x[MAX],y[MAX],n; 
void floyd() {
	for(int k = 1; k<=n; k++) {
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=n; j++) {
				dis[i][j] = min(dis[i][j],max(dis[i][k],dis[k][j]));
			}
		}
	}
} 
int main()
{
	int iCase=0;
	while(~scanf("%d",&n) && n) {
		for(int i = 1; i<=n; i++)
		for(int j = 1; j<=n; j++) dis[i][j] = 999999999;
		for(int i = 1; i<=n; i++) {
			scanf("%d%d",x+i,y+i);
			for(int j = 1; j<i; j++) {
				dis[i][j] = dis[j][i] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
			}
		} 
		floyd();
		printf("Scenario #%d\n",++iCase);
		printf("Frog Distance = %.3f\n\n",dis[1][2]);	
	}

	return 0 ;
}