ABC 218

Table of Contents

E - Destruction

https://atcoder.jp/contests/abc218/tasks/abc218_e

$C_i$ が小さい順にクラスカル法で最小全域木を作る。 使わない辺のうち、コストが負のものは捨てて、コストが正のものを答えとして計上していく。

計上しない負のコストの辺はグラフから取り除かずそのままにしている辺に相当する。

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

    vector<Edge> es(M);
    rep(i, M) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        es[i] = {a, b, c};
    }

    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    for (auto e : es)
        pq.push(e);
    dsu uf(N);
    vll dust;
    while (pq.size()) {
        auto [u, v, c] = pq.top();
        pq.pop();

        if (uf.same(u, v)) {
            if (c > 0)
                dust.push_back({c});
        } else {
            uf.merge(u, v);
        }
    }

    ll ans = 0;
    for (ll x : dust) {
        if (x > 0)
            ans += x;
    }
    cout << ans << endl;
}