POJ-2253 Frogger

题目:https://vjudge.net/problem/POJ-2253

这题先是要看懂题目，题目的大致意思就是给你n个点的坐标，其中第一个点是起点，第二个点是终点，从起点到终点肯定有很多条路径，而每一条路径中又有许多小线段组成（两个点之间的线段），让你求所有路径中最长线段的最小值。

这题可以分别用最短路径算法和最小生成树来做

1：这里我用的是dijkstra算法，先看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath> 
using namespace std;
const int maxn = 250;
const int INF = 0x3f3f3f3f;
double e[maxn][maxn],dis[maxn];
int x[maxn],y[maxn],n;
bool vis[maxn];
void solve(){
	for(int i = 1; i <= n; i++) dis[i] = e[1][i];
	vis[1] = true;
	for(int k = 1; k <= n-1; k++){
		int pos;
		double minn = INF;
		for(int i = 1; i <= n; i++){
			if(vis[i] == false && dis[i] < minn){
				pos = i;
				minn = dis[i];
			}
		}
		vis[pos] = true;
		for(int i = 1; i <= n; i++){
			dis[i] = min(dis[i],max(dis[pos],e[pos][i])); // mark
		}
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	int num = 1;
	while(1){
		scanf("%d",&n);
		if(n == 0) break;
		memset(vis,false,sizeof(vis));
		for(int i = 1; i <= n; i++){
			scanf("%d%d",&x[i],&y[i]);
		}
		for(int i = 1; i <= n; i++){
			for(int j = i+1; j <= n; j++){
				e[i][j] = e[j][i] = sqrt(double(x[i]-x[j])*(x[i]-x[j])+double(y[i]-y[j])*(y[i]-y[j]));
			}
			e[i][i] = 0;
		}
		solve();
		printf("Scenario #%d\nFrog Distance = %.3lf\n\n",num++,dis[2]);
	}
	return 0;
 } 

可以看到和dijkstra模板不一样的只是代码中我标记的那一句，这里的dis[i] 表示1号点到i号点所有路径中最长线段的最小值。我们想想要求得1号点到2号的所有路径中最长线段的最小值，除了本身1号点和2号点直接相连的距离外，肯定有某些点使得从1号点经过这些点最后到达2号点的这条路径的最长线段更优，这样就很像‘松弛’操作了，那问题又来了，怎么选中间点呢？选离1号点最近的点进行松弛操作，因为1号点到这个点本身就是一条路径，并且还是最短的，那就不存在其他点使得1号点通过其他点到达这个点的结果更优，就以这种策略不断松弛下去，最后的dis[2] 就是答案

2：最小生成树：看题解的时候看到了这种方法，正好写写复习一下相关知识点

我们将每两个点之间的距离从小到大进行排序，如果在加入某个边后使得1，2号点联通了，那么这条边就是答案，仔细想想其实很好理解，我们是从小到大进行加边的，在加入某条边后使得1，2号点联通了，那么这条边肯定在1到2的路径上，又因为是从小到大进行加边的，所以这条边一定是所有路径中最长边的最小值

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 250;
int n,x[maxn],y[maxn],f[maxn];
struct Node
{
	int x;
	int y;
	double dis;
}node[maxn*maxn];
bool cmp(Node x,Node y){
	return x.dis < y.dis;
}
void init(){
	for(int i = 1; i <= n; i++) f[i] = i;
}
int getf(int x){
	if(f[x] == x) return x;
	else{
		f[x] = getf(f[x]);
		return f[x];
	}
}

void merge(int x,int y){
	int fx,fy;
	fx = getf(x);fy = getf(y);
	if(fx != fy) f[fy] = fx;
}
int main()
{
	//freopen("in.txt","r",stdin);
	int num = 1;
	while(~scanf("%d",&n) && n){
		for(int i = 1; i <= n; i++){
			scanf("%d%d",&x[i],&y[i]);
		}
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			for(int j = i+1; j <= n; j++){
				node[++cnt].x = i;
				node[cnt].y = j;
				node[cnt].dis = sqrt(double(x[i]-x[j])*(x[i]-x[j])+double(y[i]-y[j])*(y[i]-y[j]));
			}
		}
		sort(node+1,node+cnt+1,cmp);
		double ans;
		init();
		for(int i = 1; i <= cnt; i++){
			ans = node[i].dis;
			merge(node[i].x,node[i].y);
			if(getf(1) == getf(2)) break;
			//cout<<ans<<endl;
		}
		printf("Scenario #%d\nFrog Distance = %.3lf\n\n",num++,ans);
	}
	return 0;
 } 

POJ-2253 Frogger

原文：https://www.cnblogs.com/Beic233/p/12885182.html