yuki国のお財布事情 [yukicoder No.748] - はまやんはまやんはまやん

前提知識

最小全域木

解説

最小全域木を構築するように計算していく。
プリム法がわかっていれば、それをやるだけ。
違いは、最初にK本の道路を使って、両端を連結させておくこと。
残った道路をコストで昇順ソートして、小さい方から連結させられるならさせていく操作をしていく。
連結させられないなら、削減できるということなので、答えに追加する。

int N, M, K;
int A[101010], B[101010], C[101010], E[101010], done[101010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, M) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--; B[i]--;
    }
    rep(i, 0, K) {
        cin >> E[i]; E[i]--;
    }

    UnionFind uf(N);
    ll ans = 0;
    rep(i, 0, K) {
        int e = E[i];
        int a = A[e], b = B[e], c = C[e];
        if (uf[a] != uf[b]) uf(a, b);
        done[e] = 1;
    }

    min_priority_queue<pair<int, pair<int, int>>> que;
    rep(i, 0, M) if (!done[i]) que.push({ C[i],{ A[i], B[i] } });
    while (!que.empty()) {
        int a, b, c;
        auto q = que.top();
        que.pop();

        a = q.second.first;
        b = q.second.second;
        c = q.first;

        if (uf[a] == uf[b]) ans += c;
        uf(a, b);
    }

    cout << ans << endl;
}