10034 – Freckles

A Minimum Spanning Tree graph problem.
You’re to find the MST that connects n 2D-points. To apply the MST algorithm, we need a graph first. The graph is built by connecting all the nodes (n(n+1)/2 edges each has weight equal to the distance between its ends). C++ implementation using Kruskal’s MST:

#include <algorithm>
#include <complex>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;

typedef double gtype;
typedef complex<gtype> point;
#define x real()
#define y imag()

vector<pair<gtype, pair<int, int> > > edges;

vector<int> parent;
#define setClear() parent.clear()
#define setMake() parent.push_back(parent.size())
#define setUnion(i, j) parent[setFind(i)] = setFind(j)
int setFind(int i) {
	if (parent[i] == i)
		return i;
	return parent[i] = setFind(parent[i]);
}

int main() {
	int nCase, nP;
	point p[100];
	scanf("%d", &nCase);
	while (nCase--) {
		// input
		scanf("%d", &nP);
		setClear();
		edges.clear();
		for (int i = 0; i < nP; ++i)
			setMake();
		for (int i = 0; i < nP; ++i) {
			scanf("%lf %lf", &p[i].x, &p[i].y);
			for (int j = 0; j < i; ++j)
				edges.push_back(make_pair(abs(p[i] - p[j]), make_pair(i, j)));
		}
		// kruskal's bfs
		int edgesMST = 0;
		gtype weightMST = 0;
		sort(edges.begin(), edges.end());
		while(edgesMST < nP - 1) {
			pair<gtype, pair<int, int> > e = edges[0];
			edges.erase(edges.begin());
			if(setFind(e.second.first) != setFind(e.second.second)) {
				setUnion(e.second.first, e.second.second);
				weightMST += e.first;
				edgesMST++;
			}
		}
		// output
		printf("%.2f\n", weightMST);
		if(nCase)
			printf("\n");
	}
	return 0;
}