I - Range Connect MST Editorial by nyoguta

別解

イベントソートで解くことができます。

まず、問題文を読みかえて「頂点が \(N\) 個で、\((l_i, l_{i}+1),\dots ,(r_{i}-1, r_i)\) にコスト \(c_i\) の辺が張られる」と考えても良いです (答えが \(\sum c_i\) だけずれることに注意)。

正当性の証明

クラスカル法を考えます。

頂点 \(N+i\) に関する辺を一気に処理することを考えましょう。 各処理の終了時、頂点 \(1,\dots,N\) 上の連結成分は区間を成します (区間を一気に連結にする処理なので、それはそう)。

一回の処理によって、頂点 \(N+i\) からコスト \(c_i\) の辺が「\(l_i\) から \(r_i\) に含まれる連結成分の個数」本貼られます。そしてその結果 \({l_i},\dots , {r_i}\) (と \(N+i\)) が連結になります。ところでこれは 「\({l_i},\dots ,{r_i}\) の隣り合う頂点で連結でないもの同士の間にコスト \(c_i\) の辺を貼って、ついでに適当なところと \(N+i\) をコスト \(c_i\) の辺で繋げる」と置き換えても、コストも連結性も変わりません。よって、隣り合う頂点同士にコスト \(c_i\) の辺が張られていると考えて良いです。頂点 \(N+i\) を繋げるのに必要なコストは \(c_i\) なので、頂点 \(N+i\) を削除して答えに最初から \(c_i\) を加えても問題ありません。

この問題は「\((j, j+1)\) の間に張られている辺のコストの多重集合」を multiset や map などで管理して、\(j\) を \(1\) から \(n-1\) まで増やしながら「\(l_i\) で \(c_i\) を追加する」と「\(r_i\) で \(c_i\) を削除する」というイベントを行い、最小値を見ていけば答えが出せます。

愚直に実装すると計算量は \(O((N+Q)\log Q)\) です。さらにイベントが起こらない区間を一気に処理すれば \(O(Q\log Q)\) になって \(N<10^9\) とかでも間に合います。

実装例(C++)：

#include "bits/stdc++.h"
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> events;
    long long ans = 0;

    for (int i = 0;i < q;i++) {
        int l, r, c;
        cin >> l >> r >> c;
        l--, r--;
        events.push_back({ l, c, 1 });
        events.push_back({ r, c, 2 });
        ans += c;
    }
    sort(events.begin(), events.end());

    int idx = 0;
    multiset<int> st;
    for (int i = 0;i < n - 1;i++) {
        while (idx < events.size() && events[idx][0] == i) {
            if (events[idx][2] == 1) st.insert(events[idx][1]);
            else st.erase(st.find(events[idx][1]));
            idx++;
        }
        if (st.empty()) {
            cout << -1 << endl;
            return 0;
        }
        ans += *st.begin();
    }
    cout << ans << endl;
}

posted:
last update: