[UTPC] 全域木(UTPC 2011 [F])

スポンサーリンク

概要

問題文 →
公式解説 → なさそう?

ジャッジが壊れている問題です。2021 年 4 月現在、AC が不可能だと思います。

解説がなさそうだったので書きますシリーズ。

解法

上からの評価

$K > N/2$ ならば解が存在しません。このことは、完全グラフの辺の個数が $\binom{N}{2}$ であることと、各全域木の辺の個数が $N-1$ であることから分かります。

解の構成($N$ が偶数の場合)

$K = N/2$ に対する構成方法を述べます。$K < N/2$ の場合には、それらの全域木のうち $K$ 個を出力すればよいです。

頂点を、$0$ 以上 $N$ 未満の整数と対応させておきます。$k = 0, 2, \ldots, N-2$ に対して、

  • $x\neq y$ は、$x + y\equiv k\pmod{N}$ または $x+y\equiv k+1\pmod{N}$ のとき、そのときに限り辺で結ぶ

としてグラフを作ります。こうしてできるグラフを $P_k$ と書くことにします。次が成り立ちます。

  • 各 $P_k$ はパスである
  • 任意の辺 $xy$ は、ちょうどひとつの $P_k$ に含まれる

パスであることの証明:$v$ と $v+1$ が辺を $2$ 回辿ることで行き来可能なので、連結。任意の頂点の次数が $2$ 以下なので、パスまたはサイクル。次数 $1$ の頂点があるので、パス。

$xy$ を含む $P_k$ の一意性の証明:このような $k$ は $k\equiv x+y \text{or} x+y-1\pmod{N}$ を満たすものであり、$N, k$ が偶数なので唯一である。

これで完全グラフが全域パスに分解できました。パスは木でもあるので、求めるものです。

例えば、$N=8$, $k = 0$ とすると、以下のような形になります。

これをくるくる回していって、完全グラフを分解できます。図で見るのと数式で見るのとどちらが分かりやすいでしょう?(個人差ありそう)

$N$ が奇数の場合

$K = \frac{N-1}{2}$ 個の辺素全域木をとりましょう。今回は、すべての辺を使い切る必要はありません。

ひとつの頂点を選び、避けておきます。残った $N-1$ 点に対して上述のようにパス分解 $(P_i)_i$ を作ります。そのあと、各 $P_i$ から避けておいた点にひとつ辺を張ります。最後に辺を張る操作で辺が重複しないようにすればよく、これは容易です。

例えば $N = 7$ を、$3$ つの全域木に分ける場合、次のような方法が可能です。

タイトルとURLをコピーしました