ABC 352

Table of Contents

E - Clique Connect

https://atcoder.jp/contests/abc352/tasks/abc352_e

最小全域木を構成するアルゴリズムであるクラスカル法を思いつけると解ける。 クラスカル法は辺のコストが小さい順に閉路ができないように辺を採用していくアルゴリズムである。

$C_i$ が小さい部分集合から辺を構成し順にクラスカル法で辺を張っていく。このとき、部分集合内の頂点同士が連結になりさえすれば良いので $\\{(A_1, A_j)| j \in [2, K_i], j \in \mathbb{Z} \\}$ という辺だけを考えるだけで良い。

最終的に連結グラフになっていたらそのコストを出力し、なってなかったら $-1$ を出力する。

void solve() {
    ll N, M;
    cin >> N >> M;

    vvll A(M);
    vll C(M);
    rep(i, M) {
        ll k, c;
        cin >> k >> c;
        C[i] = c;
        rep(j, k) {
            ll a;
            cin >> a;
            a--;
            A[i].push_back(a);
        }
    }

    vector<pair<ll, int>> cs;
    rep(i, M) {
        cs.push_back({C[i], i});
    }

    sort(all(cs));

    dsu uf(N);
    ll ans = 0;
    for (auto [c, i] : cs) {
        int k = A[i].size();
        rep2(j, 1, k) {
            int a = A[i][0], b = A[i][j];
            if (uf.same(a, b))
                continue;
            uf.merge(a, b);
            ans += c;
        }
    }

    if (uf.groups().size() != 1)
        ans = -1;
    cout << ans << endl;
}