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); }