样题：poj2253 题目链接

题目大意：一只青蛙需从1号石头经由一系列石头跳跃至2号石头，每块石头相隔一定距离（任意两石头均可跳），求出在所有可能的跳跃路径中，单步跳跃距离最大值最小的一条路径中，该值的大小。

向最小生成树算法方向分析，无论是prim还是kruskal算法，均是优先挑选短边或离现有生成树最近的点加入生成树，这种处理顺序就可以保证最后连上二号石头时所加上的边比之前的都要长，且不可能存在一条路径，它的最大跳跃距离比该值小（否则在路径选择时也不会选择该路径）

prim：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>


using namespace std;

#define inf 0x3f3f3f3f

double cost[202][202];
double mincost[202];
bool vis[202];
int x[202],y[202];

struct node{
    int v;
    int c;          //与生成树的距离
    bool operator < (const node& n)const{
        return c>n.c;
    }
};
int n;

double prim(){
    double res=0.0;
    for(int i=1;i<=n;i++){
        mincost[i]=inf;
        vis[i]=false;
    }
    mincost[1]=0;
    while(true){
        int v=-1;   //v在这里定义为1，保证能够排除已经使用过的mincost
        for(int i=1;i<=n;i++)
            if(!vis[i]&&(v==-1||mincost[i]<mincost[v]))
                v=i;
        vis[v]=true;
        res=max(res,mincost[v]);
        if(v==2){
            break;
        }


        for(int i=1;i<=n;i++){            //更新所有点至生成树的距离
            if(mincost[i]>cost[i][v])
                mincost[i]=cost[i][v];
        }
    }
    return res;
}

int main(){
    int Case=1;
    while(cin>>n){
        if(n==0)
            break;
        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;j<=n;j++){
                cost[i][j]=cost[j][i]=sqrt((double)((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
            }
        }
        double ans=prim();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n",Case++,ans);
    }
    return 0;
}

dijkstra算法与其写法几乎相同

最小生成树poj2253

全站热榜