UVA 534 - Frogger
题意：给定一些点。如今要求一条路径从第一个点能跳到第二个点，而且这个路径上的最大距离是最小的
思路：利用kruskal算法，每次加最小权值的边进去，推断一下是否能联通两点，假设能够了，当前权值就是答案复杂度为O(n^2log(n))
可是事实上这题用floyd搞搞O(n^3)也能过啦。
。只是效率就没上面那个方法优了
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
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;
}