TopCoder SRM 685 (Div. 1) Medium. FoxAirline2

マトロイド交差の練習です。理解が怪しいので変なことを言っているかもしれません。

この問題はマトロイド交差を使わなくても解けるので、この問題が解きたいだけなら別の解法を使いましょう。

頂点数と辺のリストが与えられる。共通する辺を持たない 2 つの全域木は作れるだろうか。

マトロイド (E, I) に対して、A1,A2∈I かつ A1∩A2={} を用いて A=A1∪A2 と表せるような A のうち要素数最大のものを求める問題をマトロイド分割問題と呼ぶ。

E を辺の集合、I を森の集合とすれば、共通する辺を持たない 2 つの森 A1, A2 の要素数の和の最大値を求める問題になるので、この問題はマトロイド分割問題である。

マトロイド分割問題はマトロイド交差問題に帰着できる。次のような 2 つの独立性オラクルを考えればいい。

I1∩I2 の要素数最大化はマトロイド分割問題に対応しており、かつマトロイド交差問題にもなっている。

したがって、マトロイド交差を O(E³ θ) で解く Edmonds のアルゴリズムを使えば解ける。

Edmonds のアルゴリズムは『組合せ最適化*1』という書籍に書かれている。きっと大学の図書館にあるはず。

グラフをうまく構築して増加パスを探すんだけど、グラフの構築が結構面倒。

『組合せ最適化』を読んでマトロイドが何なのかは分かった気がする。もう少し足を踏み入れていきたい。