AOJ2224 Save your cats

問題
N本の柱の座標が与えられ、柱と柱を繋ぐM個の壁が与えられる。
壁で囲まれた領域内に猫がいる。壁を壊して猫を助けたい。
壁を壊すコストは、壁の長さだけ掛かる。壁同士は交差しない。
すべての猫を助けるために壁を壊すコストを求めよ。

解法
問題は、「無向平面グラフから閉路をすべてなくすために取り除く必要のある辺の集合のコストを最小化せよ。」と言い換えられる。
よって、最小全域森をコストが長い辺から連結していくようにして、使わなかった辺のコストを足し合わせればよい。

using edge = tuple<int, int, double>;
vector<edge> edges;

int main() {

  int N, M; cin >> N >> M;
  vector<complex<double>> pts;
  rep(i, N) {
    double x, y; cin >> x >> y;
    pts.emplace_back(x, y);
  }
  rep(i, M) {
    int x, y; cin >> x >> y; x--, y--;
    edges.emplace_back(x, y, abs(pts[x] - pts[y]));
  }

  union_find uf(N);

  sort(all(edges), [&](const edge& a, const edge& b){ return get<2>(a) > get<2>(b); });

  double cost = 0.0;

  rep(i, M) {
    int x, y; double c; tie(x, y, c) = edges[i];
    if(uf[x] == uf[y])
      cost += c;
    else 
      uf(x, y);
  }

  printf("%.10f\n", cost);

  return 0;
}