UVA 534 - Frogger

题目链接

题意：给定一些点，现在要求一条路径从第一个点能跳到第二个点，并且这个路径上的最大距离是最小的

思路：利用kruskal算法，每次加最小权值的边进去，判断一下能否联通两点，如果可以了，当前权值就是答案复杂度为O(n^2log(n))

但是其实这题用floyd搞搞O(n^3)也能过啦。。不过效率就没上面那个方法优了

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N = 205; struct Point { int x, y; void read() { scanf("%d%d", &x, &y); } } p[N]; double dis(Point a, Point b) { int dx = a.x - b.x; int dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } struct Edge { int u, v; double d; Edge() {} Edge(int u, int v) { this->u = u; this->v = v; d = dis(p[u], p[v]); } bool operator < (const Edge& c) const { return d < c.d; } } E[N * N]; int n, en, parent[N]; int find(int x) { return x == parent[x] ? x : parent[x] = find(parent[x]); } int main() { int cas = 0; while (~scanf("%d", &n) && n) { en = 0; for (int i = 0; i < n; i++) { parent[i] = i; p[i].read(); for (int j = 0; j < i; j++) E[en++] = Edge(i, j); } sort(E, E + en); for (int i = 0; i < en; i++) { int pa = find(E[i].u); int pb = find(E[i].v); if (pa != pb) parent[pa] = pb; if (find(0) == find(1)) { printf("Scenario #%d\nFrog Distance = %.3lf\n\n", ++cas, E[i].d); break; } } } return 0; }