Clustering

题目链接：pdf

题目给出一个些点的坐标，要求把这些点分成k组，求这k组中，组和组之间的点 的最小距离d。

这道题，好像可以用Kruskal？比如：按照边长度从小到大扫描， 同时记录当前有多少个连通分量（比如：每次Union之后连通分量 的个数减一），一直到只剩k个连通分量的时候，找到下一个可用 边（这个边的两个点在不同的连通分量中）的时候退出循环。这个 可用边就是答案。

因为要求最小的d嘛，所以就是贪心吧。

所以相对难实现的就是这些了：

1. 处理输入数据
2. 带路径压缩的并查集

这些也挺好写的。

// Tue May 16 21:01:58 2017
// Tue May 16 22:06:44 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 x_root = p_find(x, parent), y_root = p_find(y, parent),
    x_size = p_size[x_root], y_size = p_size[y_root];

  if (x_size > y_size) {
    parent[y_root] = x_root;
    p_size[x_root] += y_size;
  }
  else {
    parent[x_root] = y_root;
    p_size[y_root] += x_size;
  }
}

double clustering(vector<int> x, vector<int> y, int k) {
  vector<edge> edges;

  for (size_t i = 0; i < x.size(); ++i) {
    for (size_t j = i + 1; j < y.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());
  int cc = x.size();

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

  for (auto &e : edges) {
    if (p_find(e.from, parent) != p_find(e.to, parent)) {
      if (cc == k) {
	return e.cost;
      }
      else {
	p_union(e.from, e.to, parent, p_size);
	cc--;
      }      
    }
  }

  return -1.;
} 

int main() {

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