ABC065D

https://atcoder.jp/contests/abc065/tasks/arc076_b

座標とを繋ぐ辺の重みがである時、N個の座標における最小全域木の重みを求めよという問題です。

最小全域木は名前しか知らなかったので、解説を読み、最小全域木で検索することによって、何とか解けました。

（コードは読みにくいですが）

方針としては解説の通りです（説明が面倒くさかった模様）

まず、x軸・y軸を基準に、それぞれソートします。

ここでは、各座標の添え字を残して置きたかったので、添え字を並べ替えています。

  int n; cin >> n;
  int x[n], y[n];
  vector<int> v(n), w(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    v[i] = w[i] = i;
  }

  sort(v.begin(), v.end(), [&](int a, int b) {
    return x[a] < x[b];
  });
  sort(w.begin(), w.end(), [&](int a, int b) {
    return y[a] < y[b];
  });

次に、各辺を重みでソートします。

こちらも、各辺の添え字を残して置きたかったので、添え字を並び替えています。

は、辺の重みを計算する関数です（名前が良くない）

/* typedef pair<int, int> Edge; */

  auto f = [&](Edge e) {
    int ex = abs(x[e.first] - x[e.second]);
    int ey = abs(y[e.first] - y[e.second]);
    return min(ex, ey);
  };

  int en = n * 2 - 2;
  Edge edges[en];
  int cost[en];
  vector<int> u(en);
  for (int i = 0; i < en/2; i++) {
    edges[i] = Edge(v[i], v[i+1]);
    cost[i] = f(edges[i]);
    u[i] = i;
  }
  for (int i = en/2; i < en; i++) {
    edges[i] = Edge(w[i-en/2], w[i+1-en/2]);
    cost[i] = f(edges[i]);
    u[i] = i;
  }

  sort(u.begin(), u.end(), [&](int a, int b) {
    return cost[a] < cost[b];
  });

最後に、クラスカル法を用いて、最小全域木の重みを計算します。

具体的には、重みが小さい順に辺を取り出し、その辺の座標のどちらかが初登場であれば、辺を追加するという処理をしています（Union Findを用いることで高速に行うことができる）

Union Findのコードは、ほぼ検索して出てきたものそのままなので、省略します。

（ansの型を無意識にlong longにしてしまったのですが、明らかにintで良かった）

  long long ans = 0;
  UnionFind uf(en);
  for (int i : u) {
    int p = edges[i].first;
    int q = edges[i].second;
    if (!uf.same(p, q)) {
      uf.unite(p, q);
      ans += cost[i];
    }
  }
  cout << ans << endl;

今回は、最小全域木とUnion Findという知識を増やすことができたので、嬉しかったです。

では。