UVA10034 - Freckles(最小生成树)

UVA10034 - Freckles(最小生成树)

UVA10034 - Freckles

题目大意： 
给你n个雀斑的位置，每个雀斑看作一个点，问使得这个雀斑相互连通的最短的路径长度，最小生成树的问题。

代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;const int maxn = 105;
double X[maxn], Y[maxn];
int p[maxn];void init (int n) {for (int i = 0; i < n; i++)p[i] = i;
}int getParent(int x) {return p[x] == x ? x : p[x] = getParent(p[x]);
}struct Line{int i;int j;double d;
}l[maxn * maxn];double dist (const int i, const int j) {return sqrt((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]));
}int cmp (const Line& l1, const Line& l2) {return l1.d < l2.d;
}int main () {int T;scanf ("%d", &T);while (T--) {int n;scanf ("%d", &n);init(n);for (int i = 0; i < n; i++)scanf ("%lf %lf", &X[i], &Y[i]);int cnt = 0;for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++) {l[cnt].i = i;l[cnt].j = j;l[cnt++].d = dist(i, j);    }int count = 0;double ans = 0;sort(l, l + cnt, cmp);for (int i = 0; i < cnt; i++) {if (count >= n - 1)break;int p1 = getParent(l[i].i);int p2 = getParent(l[i].j);if (p1 != p2) {ans += l[i].d;p[p1] = p2;count++;}}printf ("%.2lf\n", ans);if (T)printf ("\n");}return 0;
}