Building Roads to Connect Cities

题目链接：pdf

给出平面上的一些点，任意两点之间可以相连，求最小生成树的总权值。

用Kruskal：把所有边按照边长度升序排序，循环所有边，每次加入一个边之前要判断这个边的两个点是不是在一个集合中，如果是那么跳过，如果不是那么把这个边的两个点合并到一个集合中。集合操作用带路径压缩的并查集。循环边的过程中累加边的权值。

// Tue May 16 17:02:04 2017
// Tue May 16 20:42:10 2017

#include <bits/stdc++.h>

using namespace std;

struct edge {
  int from, to;
  double cost;
};

inline double p_distance(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int p_find(int x, vector<int> &parent) {
  int p = x;
  
  while (p != parent[p]) {
    p = parent[p];
  }
  return parent[x] = p;
}

void p_union(int x, int y, vector<int> &parent, vector<int> &p_size) {
  int p_x = p_find(x, parent), p_y = p_find(y, parent), ps_x = p_size[p_x],
    ps_y = p_size[p_y];
  
  if (ps_x > ps_y) {
    parent[p_y] = p_x;
    p_size[p_x] += ps_y;
  }
  else {
    parent[p_x] = p_y;
    p_size[p_y] += ps_x;
  }
}					       

double minimum_distance(vector<int> x, vector<int> y) {
  double result = 0.;
  vector<edge> edges;

  for (size_t i = 0; i < x.size(); ++i) {
    for (size_t j = i + 1; j < x.size(); ++j) {
      edge e; e.from = i; e.to = j; e.cost = p_distance(x[i], y[i], x[j], y[j]);
      edges.push_back(e);
    }
  }

  sort(edges.begin(), edges.end(),
       [](const edge &a, const edge &b) -> bool { return a.cost < b.cost; });
  vector<int> parent(x.size()), p_size(x.size());

  for (size_t i = 0; i < parent.size(); ++i) {
    parent[i] = i;
    p_size[i] = 1;
  }

  for (auto &e : edges) {
    if (p_find(e.from, parent) != p_find(e.to, parent)) {
      p_union(e.from, e.to, parent, p_size);
      result += e.cost;
    }
  }

  return result;
} 

int main() {
  
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  
  size_t n;
  
  while(cin >> n) {
    vector<int> x(n), y(n);
    
    for (size_t i = 0; i < n; i++) {
      std::cin >> x[i] >> y[i];
    }
    
    std::cout << std::setprecision(10) << minimum_distance(x, y) << std::endl;
  }
}