题目来源：POJ 2253
简单题目分析：
求A到B所有路径中权值最大边的最小值。
思路：
贪心，其实就是Kruskal，从一个空图开始，逐渐向里面加入最小权值的边，直到A与B连通，则最后加入的边就是答案。其实很多题目都与最小生成树有关，尤其是权值的最值问题。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int pre[205];
struct line //起点、终点及权值
{
int src;
int dest;
double len;
}temp[20005];
bool cmp(line a,line b)
{
return a.len<b.len;
}
int findRoot(int x)
{
while(x!=pre[x])
x=pre[x];
return x;
}
double getDis(int x1,int y1,int x2,int y2) //计算两点间距离
{
return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int x[205]; //记录横坐标
int y[205]; //记录纵坐标
int main()
{
int n;
int index=1;
while( ~scanf("%d",&n) && n!=0 )
{
int k=1;
int i,j;
for(i=1;i<=n;++i)
{
pre[i]=i;
int a,b;
scanf("%d %d",&a,&b);
x[k]=a;
y[k]=b;
k++;
}
k=0;
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
{
temp[k].src=i;
temp[k].dest=j;
temp[k++].len=getDis(x[i],y[i],x[j],y[j]);
}
double ans=0;
sort(temp,temp+k,cmp);
for(i=0;i<k;++i)
{
pre[findRoot(temp[i].dest)]=findRoot(temp[i].src);
if(findRoot(1)==findRoot(2)) //判断第一块石头和第二块石头是否连通
{
ans=temp[i].len;
break;
}
}
printf("Scenario #%d\n",index++);
printf("Frog Distance = %.3lf\n",ans); //这里有G++和C++的区别，在于double类型输出的区别
printf("\n");
}
return 0;
}
ps：我发现很多时候题目对于我来说，最难的地方在于怎么存储题目中所给的数据，比如这道题就需要把点的坐标存储下来，采用两个数组分别存储横纵坐标。
