kruskal.cpp

#include <cmath>
#include <iostream>
#include <queue>
#include <iomanip>

using namespace std;

typedef pair<int, int> coords;

inline double vector__length(coords pos) {
  return sqrt(pow(pos.first, 2) + pow(pos.second, 2));
}
inline coords vector__subtraction(coords a, coords b) {
  return coords(a.first - b.first, a.second - b.second);
}
inline double vector__distance(coords a, coords b) {
  return vector__length(vector__subtraction(a, b));
}

struct Edge {
  int from;
  int to;
  double cost;
  bool operator<(const struct Edge& e) const {
    return cost > e.cost;
  }
};

struct Vertex {
  int data;
  int rank;
  Vertex* parent;
};

class DisjointSet {
  vector<Vertex*> vertices;
public:
  DisjointSet(int size) {
    for (int i = 0; i < size; i++) {
      vertices.push_back(create_node(i));
    }
  }

  Vertex* create_node(int data) {
    Vertex* v = new Vertex;
    v->data = data;
    v->rank = 0;
    v->parent = v;
    return v;
  }

  Vertex* FindSet(Vertex* v) {
    if (v->parent == v) return v;

    v->parent = FindSet(v->parent);

    return v->parent;
  }

  bool Union(int v1, int v2) {
    return Union(vertices[v1], vertices[v2]);
  }

  bool Union(Vertex* v1, Vertex* v2) {
    Vertex* set_1 = FindSet(v1);
    Vertex* set_2 = FindSet(v2);

    if (set_1 == set_2) return false;

    if (set_1->rank > set_2->rank)
      set_2->parent = set_1;
    else if (set_1->rank < set_2->rank)
      set_1->parent = set_2;
    else {
      set_2->parent = set_1;
      set_1->rank++;
    }

    return true;
  }
};

int main(void) {
  int computers = 0;
  coords pos;
  vector<coords> nodes;
  priority_queue<Edge> q;

  cin >> computers;

  for (int i = 0; i < computers; i++) {
    cin >> pos.first;
    cin >> pos.second;
    nodes.push_back(pos);
  }

  for (int i = 0; i < computers; i++) {
    for (int j = i+1; j < computers; j++) {
      int distance = vector__distance(nodes[i], nodes[j]); // distance == edge
      Edge e = {i, j, distance};
      q.push(e);
    }
  }

  DisjointSet ds = DisjointSet(computers);
  double min = 0;
  while(!q.empty()) {
    Edge e = q.top();
    if (ds.Union(e.from, e.to)) {
      min += e.cost;
    }
    q.pop();
  }

  cout << fixed << setprecision(2) << min;

  return 0;
}