UVA 534 - Frogger（kruskal擴展)

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;
}