はまやんはまやんはまやん

hamayanhamayan's blog

Forest [AtCoder Petrozavodsk Contest 001 D]

https://beta.atcoder.jp/contests/apc001/tasks/apc001_d

前提知識

解法

https://beta.atcoder.jp/contests/apc001/submissions/2065311

まずは既に連結であるものはUnion Findで1つにまとめておこう。
これでグループ数がgroupになったとする。
group==1ならば、既に全て連結なので、答えは0
作るべき辺は(group - 1)本なので、使われる頂点は(group - 1)*2個である。
 
まずは、各グループ最低1つは頂点を使う必要があるので、(group-1)*2個のうちgroup個は各グループから最小のものを取ってくる。
これは各グループ毎にpriority_queueで保持しておけばいい。
あとの((group-1)*2-group)個はどこのグループから取ってきてもいい。
(上手く連結順を工夫すればなんとかなるらしい)
これも各グループで使われてない頂点を全てpriority_queueに入れて小さい方から取ってくればいい。

  • 1となるのは頂点数が(group-1)*2個無い時、つまり、上記で取ってくるときに足りなくなったら-1が答え。
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int N, M, A[101010];
min_priority_queue<int> buf[101010];
//---------------------------------------------------------------------------------------------------
ll solve() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
 
    UnionFind uf(N);
    int group = N;
    rep(i, 0, M) {
        int a, b;
        cin >> a >> b;
        if (uf[a] != uf[b]) {
            uf(a, b);
            group--;
        }
    }
 
    ll ans = 0;
    rep(i, 0, N) buf[uf[i]].push(A[i]);
    min_priority_queue<int> rest;
    rep(i, 0, N) if (uf[i] == i) {
        ans += buf[i].top(); buf[i].pop();
        while (!buf[i].empty()) {
            rest.push(buf[i].top());
            buf[i].pop();
        }
    }
 
    if (group == 1) return 0;
 
    int need = (group - 1) * 2 - group;
    while (0 < need) {
        if (rest.empty()) return -1;
 
        ans += rest.top();
        rest.pop();
        need--;
    }
 
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    ll res = solve();
    if (res < 0) printf("Impossible\n");
    else printf("%lld\n", res);
}