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