Frogger POJ - 2253（求兩個石頭之間”所有通路中最長邊中“的最小邊）

題意

題目主要說的是，有兩只青蛙，在兩個石頭上，他們之間也有一些石頭，一只青蛙要想到達另一只青蛙所在地方，必須跳在石頭上，題目中給出了兩只青蛙的初始位置，以及剩余石頭的位置，問一只青蛙到達另一只青蛙所在地的所有路徑中的“the frog distance”中的最小值，

解釋一下“the frog distance”:題目中給出了一段解釋“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.” 其中 jump range 實際上就是指一條通路上的最大邊，該詞前面的minimum就說明了要求所有通路中最大邊中的最小邊，如果直接說前面這句話你可能感覺比較繞，通過上面的解釋后我想你應該明白了吧，

通過上面的分析，不難看出這道題目的是求所有通路中最大邊中的最小邊，可以通過利用floyd,Dijkstra演算法解決該題目，注意這道題可不是讓你求兩個點之間的最短路的，只不過用到了其中的一些演算法思想，當然如果用Dijkstr演算法解決該題需要一個特別重要的方程，即

d[j] = min(d[j], max(d[x], dist[x] [j])); //dis[j]為從1號石頭到第j號石頭所有通路中最長邊中的最小邊.

如果用floyd演算法解決該題則用到方程

dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));

AC代碼

利用Dijkstra演算法：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
const int maxn = 200 + 10;
const int inf = 0x3f3f3f3f;
int x[maxn], y[maxn], vis[maxn];
double dist[maxn][maxn], d[maxn];
double solve()
{
    memset(vis, 0, sizeof(vis));
    for(int i = 1;i <= n; i++)
        d[i] = dist[i][1];
    for(int i = 1; i <= n; i++)
    {
        int x;
        double minn = inf;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && d[j] < minn)
            {
                x = j;
                minn = d[j];
            }
        }
        vis[x] = 1;
        for(int j = 1; j <= n; j++)
            d[j] = min(d[j], max(d[x], dist[x][j]));        //dis[j]為從一號石頭到第j號石頭所有通路中最長邊中的最小邊
    }
    return d[2];
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int cnt = 0;
    while(scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d %d", &x[i], &y[i]);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == j)
                    dist[i][j] = 0;
                else
                    dist[i][j] = sqrt(double(x[i] - x[j])*(x[i] - x[j]) + double(y[i] - y[j])*(y[i] - y[j]));
            }
        }
        printf("Scenario #%d\n", ++cnt);
        printf("Frog Distance = ");
        printf("%.3lf\n\n",solve());
    }
}

利用floyd演算法：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 0x3f3f3f3f;
const int maxn = 200 + 10;

int n;
double x[maxn], y[maxn];
double dist[maxn][maxn];
void Floyd()
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
        }
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int cnt = 0;
    while(cin >> n && n)
    {
        for(int i = 1; i <= n; i++)
            cin >> x[i] >> y[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == j)
                    dist[i][j] = 0;
                else
                    dist[i][j] = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
            }
        }
        Floyd();
        cout << "Scenario #" << ++cnt << endl;
        cout << "Frog Distance = " ;
        cout << fixed << setprecision(3) << min(dist[1][2], dist[2][1]) << endl << endl;

    }

}

類似題目

• 【Audiopobia UVA-10048】 （附代碼鏈接）

• Heavy Transportation POJ - 1797(不過這道題又有些不同，它是求所有通路中最短邊中的最長邊，附代碼鏈接 ）

標籤：其他

上一篇：PAT乙級1010

下一篇：玩玩24點（中）