Built? [AtCoder Beginner Contest 065 / AtCoder Regular Contest 076 D]

http://arc076.contest.atcoder.jp/tasks/arc076_b

前提知識

• 最小全域木を構築するクラスカル法
• Union-Find

解法

http://arc076.contest.atcoder.jp/submissions/1375151

今回の問題はN頂点とN^2辺のうち、コストが小さいものを使って、木を作れという問題である。
こういう、重み付き無向グラフからコストを最小化して作られた木を最小全域木(MST)と言って、構築方法にはクラスカル法とプリム法がある。
このうち、クラスカル法を使うと今回は解ける。

クラスカル法は全ての辺をコスト昇順でソートし、コストが小さい辺から両端が非連結なら連結するというのを繰り返して、MSTを作るアルゴリズムである。
今回は、辺の総和がO(N^2)なので普通にやるとTLEする。

必要な辺だけに限定してやると、少ない辺だけでMSTを考えることができる。
全ての辺をx座標でソートすると、隣り合った頂点間の辺しか使われない。
もし、違う頂点同士の辺を使うと、その間にある頂点が無駄に連結されないことになってしまう。
同様に全ての辺をy座標でソートして隣り合った頂点間の辺も利用する。
これで考える辺はO(N)となるので、後は、Union-Find辺りでクラスカル法を適用すると解ける。

typedef long long ll;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    vector<pair<int, int>> va, vb;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        va.push_back({ x, i });
        vb.push_back({ y, i });
    }
 
    vector<tuple<int, int, int>> edges;
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
    rep(i, 0, N - 1) {
        edges.push_back(make_tuple( va[i + 1].first - va[i].first, va[i].second, va[i + 1].second ));
        edges.push_back(make_tuple( vb[i + 1].first - vb[i].first, vb[i].second, vb[i + 1].second));
    }
    sort(edges.begin(), edges.end());
    
    UnionFind uf(N);
    ll ans = 0;
    for (auto p : edges) {
        int x, y, c;
        tie(c, x, y) = p;
 
        if (uf[x] != uf[y]) {
            uf(x, y);
            ans += c;
        }
    }
    cout << ans << endl;
}