锐客网

  1. 首页 > it技术 > >

poj 2253 弗洛伊德算法变形

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.
Input
The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying "Scenario #x" and a line saying "Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input

2 0 0 3 43 17 4 19 4 18 50

Sample Output
Scenario #1 Frog Distance = 5.000Scenario #2 Frog Distance = 1.414

弗洛伊德算法
基本思路：
遍历每个结点对，对每个结点对做松弛操作。结点对的松弛操作在图论里会经常用到，松弛操作用来求一个结点对之间的最短路径。假设图中有n个点，对图中结点对的松弛操作的思路为（以结点对1和n为例）：
1、建图，用一个二维数组edge[i][j]来表示i到j之间的距离。遍历每个结点对，松弛操作中edge数组表示两个点之间当前的最短距离。
2、允许经过前一个点，即2，进行中转，判断edge[1][n]和edge[1][2]+edge[2][n]之间的大小。若edge[1][2]+edge[2][n]更小，则表示通过点2中转的话1到n的距离比不中转更短。此时更新edge[1][n]的值为edge[1][2]+edge[2][n]。由于edge数组表示两个点之间当前的最短距离，则这时经过点2中转的结果已经隐含体现在了edge[1][n]中，之后的松弛操作都是在这一基础上进行。
2.1、然后允许经过前两个点，即2、3，进行中转，判断edge[1][n]和edge[1][3]+edge[3][n]之间的大小，若edge[1][3]+edge[3][n]更小，则表示通过点3中转的话1到n的距离比不中转更短。此时更新edge[1][n]的值为edge[1][3]+edge[3][n]。由于edge数组表示两个点之间当前的最短距离，则这时经过点2、3中转的结果已经隐含体现在了edge[1][n]中，之后的松弛操作都是在这一基础上进行。
3、重复2过程，允许经过前3~n-1个结点进行中转，保存每一次中转与否最短路径的变化。最后得到的edge[1][n]就是1到n的最短路径的路径和。
4、对图中的每一个结点对都进行松弛操作，此时edge[i][j]，就是从i到j的最短路径，不管i和j是几，都能得到答案。

#include #define inf 999999//表示两个点之间不连通 #define max 105 using namespace std; int m,n,edge[max][max]; int main() { int i,j; cin>>n>>m; //先对邻接矩阵进行初始化 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) edge[i][j]=inf; edge[i][i]=0; } //建图 while(m--) { cin>>i>>j; cin>>edge[i][j]; edge[j][i]=edge[i][j]; } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) //若结点对跟中转点不连通，则跳过 if(edge[i][k]!=inf && edge[k][j]!=inf && edge[i][j]>(edge[i][k]+edge[k][j])) //更新最短路径 edge[i][j]=edge[i][k]+edge[k][j]; cout<


题中求得是青蛙一次至少跳多远才能成功到达对方所在的地方；即求所有路径中每条路径中的最大距离的最小值（求一条1~2的路径使得路径上的最大边权最小）
floyd中更新距离改成更新最小的最大边权；
#include #include #include #include using namespace std; const int inf=0x3f3f3f3f; const int N=220; double G[N][N]; int n,id; struct node{ int x; int y; node(){ } node(int xx,int yy){ x=xx; y=yy; } }nd[220]; void Floyd(){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ for(int k=1; k<=n; k++){ G[j][k]=G[k][j]=min(G[j][k],max(G[j][i],G[i][k])); } } } //cout<

【poj 2253 弗洛伊德算法变形】

    推荐阅读


    上一篇：高并发服务器处理

    下一篇：如何熟悉一个系统（（内含知识大图））