ARC225 C - K Spanning Tree

考え方

まず、重みの上限と下限を考える。

重みの下限は、重み $1$ の辺を最低限いくつ使わなければならないかである。
つまり、重み $0$ の辺だけで Union-find 木を作り、連結成分数 $-1$ がその答えである。
また、その重みの全域木を作れるかという問いにも、簡単に作れるといえる。
重み $0$ の辺でできた連結成分ごとに木を作り、その森を重み $1$ の辺で連結すればいい。

重みの上限は、重み $0$ の辺について同様に考えればよい。

さて、では下限が $L$ で上限が $U$ だった場合に $L \leq x \leq U$ の範囲の重み $x$ の全域木が全て作れるか？
これは、可能である。
以下、証明。

重み $L$ である全域木を $G_1$、重み $U$ である全域木を $G_2$、とする。
これらが作れることは証明済である。

最初のグラフとして、$G_1$ を用意する。
ここに、グラフが $G_2$ に一致するまで以下を繰り返す。

• $G_2$ に含まれるが現在のグラフに含まれない辺を $1$ つ選び、現在のグラフに加える
• 辺を加えたせいで、どこかにサイクルが発生している
• $G_2$ は木なので、サイクル中に $G_2$ に含まれない辺がある
• そのうち任意の $1$ つを取り除く

この操作は $G_2$ に一致するまで続けることができ、重みは一度に最大 $1$ しか増減しない。
したがって、$L \leq x \leq U$ の範囲の重み $x$ の全域木は全て作れる。

これで、"Yes" か "No" かで答える問題であれば解けた。
さて、では実際の構築を考える。
もちろん上の方法を実装できるならそれでもよいが、おそらく非常に難しい。

ということで、作れることがわかっている前提での作り方を実行する。

まず、重み $0$ の辺だけで Union-find 木を作ったとき、重み $1$ の辺が最低何本必要か考えた。
その最低限の個数の重み $1$ の辺の組の例を $1$ つ作り、それらの辺を全て採用する。
重み $1$ の辺だけで Union-find 木を作ったとき、重み $0$ の辺が最低何本必要かも考えた。
その最低限の個数の重み $0$ の辺の組の例を $1$ つ作り、それらの辺を全て採用する。

この時点で、$K$ が作れる範囲の数であれば、重さ $0$ の辺も重さ $1$ の辺も個数が超過はしていない。
そして、残った連結成分は、重み $0$ の辺だけでも、重み $1$ の辺だけでも、他の連結成分と連結できる。
ということは残りは、各重みの残り本数に気をつけて、連結成分を新しく結べる辺を自由に選んでよい。
重み $0$ も重み $1$ も、全体の重みを $K$ にするための規定本数になったら構築終了。

入力例1での動作

入力例1の $1$ つ目のテストケースのみ考える。

入力を受け取り、辺の両端を 0-indexed に直す。

n: 4
m: 5
k: 2

$2$ つの Union-Find木 を作る。
重み $0$ の辺だけを加えた d0 と、重み $1$ の辺だけを加えた d1 を作る。
それぞれの連結成分は次のようになる。

d0: {0, 1, 2}, {3}
d1: {0}, {1, 2, 3}

左のグラフが d0、中央のグラフが d1、右のグラフが最終結果用の d である。
また、赤い辺が重み $0$ の辺、青い辺が重み $1$ の辺である。

d0 の連結成分数が $2$ なので、重み $1$ の辺が最低 $1$ 本必要。
d1 の連結成分数が $2$ なので、重み $0$ の辺が最低 $1$ 本必要。
よって、全域木を作る $3$ 本の辺の重み合計は、$1$ 以上 $2$ 以下となる。
今回は $2$ であるため、作成可能ということになる。

重み $0$ の辺の残り本数を count0 $=1$、重み $1$ の辺の残り本数を count1 $=2$ とする。

最終結果用の Union-Find木 d を作る。

まず、最低限必要な辺を確保する。

辺 $0$ は重み $0$ であり、d1 では頂点 $0$ と頂点 $1$ が連結でないので採用する。
result に $0$ を追加し、count0 $=0$ とする。
d と d1 で、頂点 $0$ と頂点 $1$ を連結させる。

辺 $1$ と $2$ は、重み $0$ で、d1 上で既に連結になっているので見送る。

辺 $3$ は重み $1$ であり、d0 では頂点 $3$ と頂点 $1$ が連結でないので採用する。
result に $3$ を追加し、count1 $=1$ とする。
d と d0 で、頂点 $3$ と頂点 $1$ を連結させる。

辺 $4$ は、重み $1$ で、d0 上で既に連結になっているので見送る。

この時点で、目的の木を管理する d の連結成分は次のようになる。

d: {0, 1, 3}, {2}

次に、各重みの残り本数を見ながら、残りの連結成分をつなぐ。

辺 $0$ は採用済。

辺 $1$ と $2$ は重み $0$ の残り本数が $0$ なので、見送る。

辺 $3$ は採用済。

辺 $4$ は重み $1$ であり、d では頂点 $3$ と頂点 $2$ が連結でない。
count1 $=1$ なのでこの辺を採用し、result に $4$ を追加して count1 $=0$ とする。
これにより、d の全頂点が連結になる。

result には $0$, $3$, $4$ が入っている。
1-indexed に直して $1\ 4\ 5$ を出力する。

注意点

特になし。

別解

特になし。