本文共 2579 字，大约阅读时间需要 8 分钟。
#include#include #include #include #include using namespace std;const int maxn = 40000 + 5;int n, pos;double max_len;struct coordinate{ int x, y;} coor[205];struct node{ int op; int ed; double len; bool operator < (const node Next) const { return len < Next.len; }} edge[maxn];int root[205];inline double dis(coordinate temp1, coordinate temp2){ int x = temp1.x - temp2.x; int y = temp1.y - temp2.y; return sqrt(x * x + y * y);}int Find(int x){ return x == root[x] ? x : root[x] = Find(root[x]);}void Kruskal(){ for(int i = 0; i <= n; i ++) root[i] = i; sort(edge, edge + pos); max_len = 0; for(int i = 0; i < pos; i ++) { int x = Find(edge[i].op); int y = Find(edge[i].ed); if(x != y) { root[y] = x; if(Find(0) == Find(1)) //如果已经从0走到1 { max_len = edge[i].len; //因为edge[]已经从小到大排过序，所以最后一次使01连通的一定是最大的边值 break; //找到最大的边值 跳出 } } }}int main(){ int cas = 0; while(~scanf("%d", & n) && n) { for(int i = 0; i < n; i ++) scanf("%d %d", & coor[i].x, & coor[i].y); pos = 0; for(int i = 0; i < n; i ++) for(int j = i + 1; j < n; j ++) { edge[pos].op = i; edge[pos].ed = j; edge[pos].len = dis(coor[i], coor[j]); pos ++; } Kruskal(); printf("Scenario #%d\n", ++ cas); printf("Frog Distance = %.3f\n\n", max_len); } return 0;}
题意：
（摘自 永夜初晗凝碧天） 题目大意，有两只青蛙，分别在两个石头上，青蛙A想要到青蛙B那儿去，他可以直接跳到B的石头上，也可以跳到其他石头上，再从其他石头跳到B那儿，求青蛙从A到B的所有路径中最小的Frog Distance，我们定义Frog Distance为从A到B的一条路径中所跳的最大距离，例如，如果从A到B某条路径跳的距离是2，5，6，4，则Frog Distance就是6，题目输入的第一行代表石头的个数，当个数为0时结束程序，接着有n行，其中第2，3行分别代表A，B青蛙的坐标，其他n-2行分别代表空的石头的坐标，输出一个小数（保留三位），具体格式参见样例，注意没输出一个答案还要再空一行。 题目数据1很明显为5.000 对于数据2青蛙有两种方案 方案1：1-2则经过距离为2.000故此时Frog Distance=2.000 方案2：1-3-2 则经过距离分别是1.414 1.414 故此时Frog Distance=1.414 故所求的最小的Frog Distance=1.414 题解： 这道题的题意比较绕吧。不过上面摘过来的题意我觉得解释的比较清楚。之后我把这道题当成最小生成树，用了Kruskal来做。但是这道题有点不同，只要小边不断连接，只要01连通即可（可以跳出了）。（这题我的下标从0开始的，这上面我也是WA了几遍 因为老思想的模板 我root是从1开始的….）。其实我对Kruskal理解的也不是很透彻，一开始不知道怎么设起点 终点之类的奇葩问题..后来慢慢理解了Kruskal只是按最小的边排序，用最小的两点距离连通全部的点，并没有起点终点之分..这道题可以这样理解，这只青蛙比较懒，他跳石头的时候希望两个石头间的距离越小越好（跳的短一点 省力），跳多少次（跳的总距离）无所谓的（当然也是越短越好啦）。（而我平时做的题是要总距离最小吧 和这个题是不一样的）。要怎么达到两个石头间的距离越小越好呢。就是用sort从小到大排序。如何筛选出跳的最远的两个石头的距离代码上说明白了。因为每次都是用小边把两点连起来（是不是起始点开始无所谓 有没有和起始点连通无所谓 都一视同仁处理连接）直到将01连通（说明前面有的小边是有用的 或者 直接01连通）。
转载地址：http://nctpi.baihongyu.com/