poj 2253 Frogger（floyd变形）

题目链接：http://poj.org/problem?id=1797

题意：给出两只青蛙的坐标A、B，和其他的n-2个坐标，任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路，每一条通路的元素都是这条通路中前后两个点的距离，这些距离中又有一个最大距离。现在要求求出所有通路的最大距离，并把这些最大距离作比较，把最小的一个最大距离作为青蛙的最小跳远距离。

有一个明显的方法就是dfs一遍但是肯定会te，所以可以考虑一下用dp的思想。

类似记忆化搜索的思想，由于数据比较小所以不用记忆化搜索也行直接利用套3层for

dp[i][j]表示从i点到j点的minimax distance（就是题目所要求的）mmp[i][j]表示i

点到j点的距离。

for(int k = 1 ; k <= n ; k++) {

for(int i = 1 ; i <= n ; i++) {

for(int j = 1 ; j <= n ; j++) {

MIN = max(mmp[i][k] , mmp[k][j]);

MIN2 = max(dp[i][k] , dp[k][j]);

dp[i][j] = min(dp[i][j] , min(MIN , MIN2));

dp[j][i] = dp[i][j];

}

其实这3层for也是利用了floyd的思想。

#include <iostream>

#include <cstring>

#include <string>

#include <cmath>

#include <cstdio>

using namespace std;

double mmp[210][210] , dp[210][210] , MIN , MIN2;

int n , x , y;

struct TnT {

    int x , y , num;

};

bool vis[220];

int main() {

    int ans = 0;

    while(scanf("%d" , &n)) {

        ans++;

        if(!n)

            break;

        TnT T[210];

        for(int i = 1 ; i <= n ; i++) {

            scanf("%d%d" , &x , &y);

            T[i].num = i;

            T[i].x = x;

            T[i].y = y;

        }

        for(int i = 1 ; i <= n ; i++) {

            for(int j = 1 ; j <= n ; j++) {

                mmp[i][j] = (double)400000;

                dp[i][j] = (double)400000;

            }

        }

        for(int i = 1 ; i <= n; i++) {

            int x1 = T[i].x , y1 = T[i].y , pos1 = T[i].num , x2 , y2 , pos2 , m;

            for(int j = 1 ; j <= n ; j++) {

                x2 = T[j].x , y2 = T[j].y ,  pos2 = T[j].num;

                m = 1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2);

                mmp[pos1][pos2] = min(mmp[pos1][pos2] , 1.0 * sqrt(double(m)));

                mmp[pos2][pos1] = min(mmp[pos1][pos2] , mmp[pos2][pos1]);

            }

        }

        for(int k = 1 ; k <= n ; k++) {

            for(int i = 1 ; i <= n ; i++) {

                for(int j = 1 ; j <= n ; j++) {

                    MIN = max(mmp[i][k] , mmp[k][j]);

                    MIN2 = max(dp[i][k] , dp[k][j]);

                    dp[i][j] = min(dp[i][j] , min(MIN , MIN2));

                    dp[j][i] = dp[i][j];

                }

            }

        }

        printf("Scenario #%d\n" , ans);

        printf("Frog Distance = %.3f\n\n" , dp[1][2]);

    }

    return 0;

}

巴特西

poj 2253 Frogger（floyd变形）

最新文章

热门文章