好几天没更新博客了，因为这周在看关于图论的算法，有好几个（还是英文名字-_-||），人晕晕的......
说一下这个Frogger吧。这个题目的话......难的不是做法，而是题意。。。
大致题意：有两只青蛙A和B，都在湖里的石头上（湖里还有其他石头），现在A要去B的位置，方法是借助其他石头跳过去，求的是所有可达路径中，权值（石头之间的距离）最大的是多少。
每组案例的第一组和第二组数据分别是青蛙A和青蛙B的坐标。这么说吧，求最小生成树的最大权。
尴尬的是写的是混合语言啊，不会用操纵符（-_-||）。新手，对算法还不是很了解，请多多体谅！！！
Sample Input
2 // 石头（点）的个数N，下面N行是石头的坐标
0 0
3 4
3
17 4
19 4
18 5
0
Sample Output（注意结果从#1开始，并且每次输出空一行，结果保留三位小数）
Scenario #1 Frog Distance = 5.000
Scenario #2 Frog Distance = 1.414
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define size 220 6 using namespace std; 7 8 struct point//石头（图的顶点） 9 { 10 double x,y; 11 }p[size]; 12 13 double stone[size][size],dis[size];//一个存图，一个存点之间的距离（权） 14 int N,T,i,j,flag[size];//flag存标记的 15 double a,b,ans,tem,minx; 16 17 double distance(double x1,double y1,double x2,double y2) 18 { 19 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//两点之间的距离 20 } 21 22 void Init()//初始化两个数组 23 { 24 memset(flag,0,sizeof(flag)); 25 memset(stone,0,sizeof(stone)); 26 } 27 28 double Prim() 29 { 30 ans=0; 31 int key; 32 double temp=0xfffffff;//先来一个大数 33 for(i=1;i<=N;i++) 34 dis[i]=stone[1][i];//存上各自的距离（权） 35 flag[1]=1;//咱们先从1号位置开始遍历 36 for(i=1;i<N;i++) 37 { 38 minx=temp; 39 for(j=1;j<=N;j++) 40 if(flag[j]!=1&&dis[j]<minx)//找到没有遍历过的点并且它周围权值最小的边 41 { 42 minx=dis[j];//把这条边的权设置为最小，下次就跟它比较了 43 key=j;//记录一下这个点 44 } 45 if(ans<minx) 46 ans=minx;//记录一下距离 47 if(key==2)//到终点了，结束 48 break; 49 flag[key]=1;//这个点已经来过了 50 for(int j=1;j<=N;j++)//维护这棵树（取权值较小的） 51 { 52 if(flag[j]!=1&&stone[key][j]<dis[j]) 53 dis[j]=stone[key][j]; 54 } 55 } 56 return ans; 57 } 58 59 int main() 60 { 61 T=1; 62 while((cin>>N),N) 63 { 64 Init(); 65 for(i=1;i<=N;i++) 66 cin>>p[i].x>>p[i].y;//输入坐标 67 for(i=1;i<=N;i++) 68 for(j=1;j<=N;j++) 69 stone[i][j]=stone[j][i]=distance(p[i].x,p[i].y,p[j].x,p[j].y);//两点的距离（a到b等效b到a） 70 cout<<"Scenario #"<<T<<endl; 71 printf("Frog Distance = %.3lf ",Prim());//这里有点尴尬(-_-||) 72 cout<<endl; 73 T++; 74 } 75 return 0; 76 }