poj2253-Frogger

题目传送：poj2253
题目大意：青蛙A通过跳跃小石头的方式跳到青蛙B那里去，给出青蛙A和青蛙B以及其他小石头的坐标。A到B的任一路径中包含若干中间距离，找出最大中间距离。注意该题求的是所有路径的最大中间距离中值最小的那个。

dijkstra
一毛一样的代码，c++过了，g++过不了，g++对double类型数据编译时精度不够，遇到这种情况试试换c++编译吧

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=255;
const int inf=1e9;
int x[maxn],y[maxn];
int n,book[maxn];
double e[maxn][maxn];
double dis[maxn];
void dij(int s){
    for(int i=1;i<=n;i++){
        int mmin=inf;
        int k=-1;
        //int k;
        for(int j=1;j<=n;j++){
            if(book[j]==0&&dis[j]<mmin){
                mmin=dis[j];
                k=j;
            }
        }
        if(k==-1)break;
        book[k]=1;
        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],max(dis[k],e[k][j]));//dis[j]为从一号石头到第j号石头所有通路中最长边中的最小边
        }
    }
}
int main(){
    int cnt=0;
    while(~scanf("%d",&n)){
        if(n==0)break;
        memset(e,0,sizeof(e));//memset二维数组初始化
        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+1;j<=n;j++){
                e[i][j]=e[j][i]=sqrt(double((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
            }
        }
        for(int i=1;i<=n;i++)
            dis[i]=inf;
        dis[1]=0;
        memset(book,0,sizeof(book));
        //book[1]=1;没有对源点1的出边松弛，所以不标记
        dij(1);
        printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++cnt,dis[2]);
    }
    return 0;
}

最小生成树：
学习到一个很巧妙的方法，算出所有点之间的距离，将距离从小到大排序，逐一选边，将边的两点加入到一个集合里，并判断两只是否相遇，若相遇，此时距离就是答案

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=255;
int pre[maxn];
int px[maxn],py[maxn];
struct point{
    int x,y;
    double dis;
}s[maxn*maxn];//不能开太小，s[maxn]出错
int Find(int x){ //判断是否在一个集合里
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}
void merg(int x,int y){ //并查集思想
    int m=Find(x);
    int n=Find(y);
    if(m!=n)
        pre[n]=m;
}
bool cmp(point a,point b){
    return a.dis<b.dis;
}
int main(){
    int cas=0;
    int n;
    while(~scanf("%d",&n)){
        if(n==0)break;
        for(int i=1;i<=maxn;i++)
            pre[i]=i;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&px[i],&py[i]);
        }
        int cnt=1;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                s[cnt].x=i;
                s[cnt].y=j;
                //s[cnt].dis=sqrt(double(pow(px[i]-px[j],2)+pow(py[i]-py[j],2)));//编译没过
                s[cnt].dis=sqrt(double((px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j])));
                cnt++;
            }
        }
        sort(s,s+cnt,cmp);
        double ans;
        for(int i=1;i<=cnt;i++){
            ans=s[i].dis;
            merg(s[i].x,s[i].y);
            if(Find(pre[1])==Find(pre[2]))
                break;
        }
        printf("Scenario #%d\n",++cas);
        printf("Frog Distance = %.3lf\n\n",ans);
    }
}