POJ 2253 Frogger （求某两点之间所有路径中最大边的最小值）

题意：有两只青蛙，a在第一个石头，b在第二个石头，a要到b那里去，每种a到b的路径中都有最大边，求所有这些最大边的最小值。
思路：将所有边长存起来，排好序后，二分枚举答案。

　　时间复杂度比较高，344ms。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

const int maxn=;

const int INF=0x3f3f3f3f;

double w[maxn][maxn]; //存储边长

double wlen[];

int con[maxn][maxn]; //con[i][j]=1表示i、j连通，con[i][j]=0表示不连通

int idx;

int n;

struct Node{

    int x,y;

}node[maxn];

int main()

{

    int t=,a,b;

    double length;

    int ans;

    while(scanf("%d",&n)!=EOF){

        if(n==)

            break;

        t++;

        idx=;

        memset(w,,sizeof(w));

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

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

            scanf("%d%d",&a,&b);

            node[i].x=a;

            node[i].y=b;

        }

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

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

                //pow传递的参数先要强制转换成double，否则提交编译错误

                length=pow(double(node[j].x-node[i].x),)+pow(double(node[j].y-node[i].y),);

                length=sqrt(length);

                w[i][j]=w[j][i]=length;

                wlen[idx++]=length;

            }

        }

        sort(wlen,wlen+idx);

        //二分枚举所有可能的值，floyd的时候考虑所有长度不大于该值的边

        int l=,r=idx-,mid;

        while(l<=r){

            mid=(l+r)>>;

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

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

                    //初始化，con[i][j]=1表示边i、j长度不大于枚举值，=0表示大于枚举值

                    if(w[i][j]>wlen[mid])

                        con[i][j]=con[j][i]=;

                    else

                        con[i][j]=con[j][i]=;

                }

            }

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

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

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

                        //只要有一对con[i][k]、con[k][j]连通，con[i][j]就连通

                        con[i][j]|=con[i][k]&con[k][j];

                    }

                }

            }

            if(con[][]){

                r=mid-;

                ans=mid;

            }

            else{

                l=mid+;

            }

        }

        printf("Frog Distance = %.3lf\n",wlen[ans]);

        puts("");

    }

    return ;

}

这里附上别人的代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

double dist[][]; //dist[i][j]表示i到j的路径中边的最大值的最小值

int n;

struct Node {

    int x;

    int y;

} e[];

void Floyd() {

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

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

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

                if(max(dist[i][k],dist[k][j])<dist[i][j])

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

            }

        }

    }

}

int main() {

    int t=;

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

        if(n==)break;

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

            scanf("%d%d",&e[i].x,&e[i].y);

        }

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

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

                dist[i][j]=sqrt(pow((double)(e[i].x-e[j].x),)+pow((double)(e[i].y-e[j].y),));

            }

        }

        Floyd();

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

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

    }

}