[JOI] plugs(2010年春合宿)

スポンサーリンク

概要

問題文 →  
公式解説 → なさそう??
自分の提出 →

完全マッチングの一意性という、難しそうな条件が与えられています。

手段は限られていそうで「簡単に解けるならばきっとこういうことが成り立つだろう」とでも予想できればそのまま解けてしまうような問題。ちゃんと証明せず解けてしまう人も割と居ると思います。

調べても証明を記述している方が見当たらなかったので、書いておきます。

補題

細かいところを無視すれば、おおよそ次の問題です。

$2$ 部グラフ $G=(V,E)$ ($V = A\amalg B$ で全ての辺は $AB$ 間を結ぶ)がある。$G$ は唯一の完全マッチング $M$ を持つことが分かっている。$M$ を復元せよ。

完全マッチングの一意性から、次を示すことができます。

【補題】二部グラフ $G=(A\amalg B,E)$ が唯一の完全マッチングを持ち、$|A| = |B|\geq 1$ であるとき,$\deg(a) = 1$ となる $a \in A$ が存在する。

証明

任意の $a\in A$ が $\deg a \geq 2$ を満たすと仮定します。次のように長さ無限大の歩道 $W = a_1b_1a_2b_2\cdots$ をとります。

  • $a_1\in A$ を適当にとる($|A| \geq 1$ より可能)
  • $a_i$ までとったとき、$a_ib_i\notin M$ となる $b_i\in B$ をとる($\deg a_i\geq 2$ より可能)
  • $b_i$ までとったとき、$b_ia_{i+1}\in M$ となる $a_{i+1}\in A$ をとる($M$ が完全マッチングなので一意存在)

$W$ は「交互歩道」つまり、$M$ に属する辺とそうでない辺を交互に用いています。$W$ は(有限グラフ上の)長さ無限大の歩道なので、サイクルを含みます。それをひとつとり、$C$ とします。

$G$ は二部グラフで、$C$ の長さは偶数です。
また、$C$ は $M$ に属する辺とそうでない辺を交互に用いています。したがって、$C$ 上の辺について $M$ に属するかどうかを入れ替えることで、新しい完全マッチング $M’$ が得られます。$G$ 上の完全マッチングの一意性に矛盾するので証明できました。

問題の解法

上記の補題より次数 $1$ の点の存在が保証されます。この点のマッチング相手は決まる。これらの $2$ 頂点を除いたグラフて再帰的に同じ問題を解けばよいです。

次数 $1$ の頂点の検出を、累積和などを用いて高速化する必要があります。

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