[デンソークリエイトプログラミングコンテスト2022(ABC239)]F - Construct Highway
[Q] https://atcoder.jp/contests/abc239/tasks/abc239_f
1. 作られるのは木
2. なので、D[]の総和は(N-1)*2になるはずだし、
3. ループするような連結は許容されない。
4. UnionFindを考える。
5. 最終的に1つのグループになるはずなので、
(a) 入力値を処理するときには、親に足を集める
(b) 木の探索をするときには、頂点0に足を集める。
6. D[]が2以上の頂点と頂点0を連結させ、D[0]の足を増やす。
7. 最後にD[]が1の頂点と頂点0を連結して、葉を増やす。
8. つじつまがあえばYes。
シミュレートする
N=6 M=2
D: 1 2 1 2 2 2
2 3
1 4
1. 入力値Mをuniteしていく。
・2 3を連結
par[3] = 2
--D[2]
--D[3]
・1 4を連結
par[4] = 1
--D[1]
--D[4]
2. 足の本数をqueueに詰める。
D: 0 1 0 1 2 2
par[1] = 1: Q[1] = {}
par[2] = 2: Q[2] = {2}
par[3] = 2: Q[2] = {2} + {}
par[4] = 1: Q[1] = {} + {4}
par[5] = 5: Q[5] = {5, 5}
par[6] = 6: Q[6] = {6, 6}
以上から、
Q[1] : {4}
Q[2] : {2}
Q[3] : {}
Q[4] : {}
Q[5] : {5,5}
Q[6] : {6,6}
D: 1 1 0 0 2 2
6. 足を D[1] に集めながら連結させる。
まずは D >= 2 の頂点から。
・D[5] >= 2 なので 1と5 を連結する。
par[5] = 1
Q[1]とQ[5]から1本ずつ失って、
Q[1] = {4} -> {}
Q[5] = {5,5} -> {5}
失った2要素がansになる。
ans = {4, 5}
Q[5]の残りは、Q[1]に移植される。
Q[1] = {5}
Q[5] = {}
・D[6] >= 2 なので、1 と 6 を連結する。
ans += {5, 6}
Q[1] = {6}
Q[6] = {}
7. D>=2がなくなったので、D==1と足1を連結する。
D: 1 1 0 0 0 0
・D[2] == 1 なので、足1と連結。
Q[1] = {}
Q[2] = {}
ans += {6, 2}
以上で、{4, 5} {5, 6} {6, 2}実装
ll N, M;
ll D[200020];
queue<ll> Q[200020];
int main() {
cincout();
cin >> N >> M;
ll road_sum = 0;
rep(i, N) {
cin >> D[i];
road_sum += D[i];
}
if (road_sum != (N - 1) * 2) {
cout << -1 << endl;
return 0;
}
UnionFind tree(N);
rep(i, M) {
ll a, b;
cin >> a >> b;
--a, --b;
if (D[a] == 0 || D[b] == 0 || tree.issame(a, b)) {
cout << -1 << endl;
return 0;
}
--D[a], --D[b];
tree.unite(a, b);
}
// uniteされているものを親に集める
rep(i, N) {
ll p = tree.root(i);
rep(j, D[i]) { Q[p].push(i); }
}
ll s = 0; // 親
queue<pll> ans;
// 2個以上を統括
for (ll i = 1; i < N; ++i) {
if (tree.issame(s, i)) continue;
if (Q[i].size() > 1) {
if (Q[s].empty()) {
cout << -1 << endl;
return 0;
}
tree.unite(s, i);
ans.push({Q[s].front(), Q[i].front()});
Q[s].pop();
Q[i].pop();
while (!Q[i].empty()) {
Q[s].push(Q[i].front());
Q[i].pop();
}
}
}
// 1個を統括
for (ll i = 1; i < N; ++i) {
if (tree.issame(s, i)) continue;
if (!Q[i].empty()) {
tree.unite(s, i);
if (Q[s].empty()) {
cout << -1 << endl;
return 0;
}
ans.push({Q[s].front(), Q[i].front()});
Q[s].pop();
Q[i].pop();
}
}
rep(i, N) {
if (!Q[i].empty() || (tree.size(i) != 0 && tree.size(i) != N)) {
cout << -1 << endl;
return 0;
}
}
while (!ans.empty()) {
auto &[a, b] = ans.front();
cout << a + 1 << " " << b + 1 << endl;
ans.pop();
}
}