7K12 blog

猫でも分かる何か

ABC318D - General Weighted Max Matching (dif1017)

順番は無関係なので i \lt jで固定して赤黒木のような感じでDFSする。白線では遷移自体はせず赤線で遷移する。完全グラフの完全マッチングは「残った頂点のうち最も小さい番号の頂点に対して相手を選ぶ」を繰り返すことで数え上げることが出来る。残った頂点のうち最も小さい番号を選ぶのは1通り、最も小さい番号の相手は(既にk個の頂点を選んでいたとして)n-k-1通り。計算量は  O((n-1)!!)

https://atcoder.jp/contests/abc318/submissions/48615381

今までC(n,2)の総積だと思っていてngtkanaさんに数え方を教えてもらった。

例えば、下図の競争の順位を決めるときは4×3×2通り。掛け算での数え上げには番号や順位を決めるという意味があって、完全グラフの完全マッチングではA-B-CとC-B-Aを同じカウントにしなければならない。