UVa 10034 Freckles

題意：
    給你N個二維點座標，要找出把這N個點連在一起成一個Set的最短路徑
想法：
    先將點與點兩兩之間的邊長先算出來並排序，然後用Kruskal演算法，找出最小生成樹，並在找的時候同時將邊長累加起來最後即是答案。

	#include <cstdio>
	#include <cmath>
	#include <algorithm>
	using namespace std;
	struct point{
	double x;
	double y;
	}P[105];
	struct edge {
	int i_a;
	int i_b;
	double L;
	}E[105*105];
	int Set[105];
	double Ans;
	bool cmp (edge A, edge B);
	void Set_Initial(int N);
	int Find_Root(int x);
	bool Union(edge A);
	int main()
	{
	int Case, N;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
	scanf("%lf%lf", &P[i].x, &P[i].y);
	int nOfE = 0;
	for (int i = 0; i < N; ++i) {
	for (int j = i + 1; j < N; ++j) {
	double Len = sqrt(pow(P[i].x - P[j].x, 2) + pow(P[i].y - P[j].y, 2));
	E[nOfE++] = {i,j,Len};
	}
	}
	sort (E, E + nOfE, cmp);
	Set_Initial(N);
	for (int i = 0, sum = 0; sum != N - 1; ++i) {
	if (Union(E[i])) sum++;
	}
	printf("%.2f\n", Ans);
	if (Case) putchar('\n');
	}
	}
	bool cmp (edge A, edge B)
	{
	return A.L < B.L;
	}
	void Set_Initial(int N)
	{
	Ans = 0;
	for (int i = 0; i < N; ++i){
	Set[i] = i;
	}
	}
	int Find_Root(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = Find_Root(Set[x]);
	}
	bool Union(edge A)
	{
	int x = Find_Root(A.i_a);
	int y = Find_Root(A.i_b);
	if (x != y) {
	Set[x] = y;
	Ans += A.L;
	return true;
	}
	return false;
	}

view raw [UVa] 10034 Freckles.cpp hosted with ❤ by GitHub