Codeforces Round #603 (Div. 2) F. Economic Difficulties

非想定解っぽいですがまとめておきます。

問題概要

問題文中の図のように、一列に並んだ $n$ 個のノードを挟むように根付き木が2つ与えられる。それぞれの頂点数は $a, b$ であり、葉の数はいずれも $n$ で、それぞれの木について各ノードごとに1個の葉が接続されている。問題文中の図のようにこれらを図示するとき、辺が交差することはない。

このグラフからできるだけ多くの辺を取り除きたい。ただし全てのノードは、根付き木のうち少なくとも片方について「そちらの根付き木の辺を辿って根と接続されている」状態でなければならない。取り除ける辺の最大本数を求めよ。

制約

$1 \le n \le 1000$
$1+n \le a, b \le 1000+n$
与えられるグラフはそれぞれ頂点1を根とする根付き木であり、葉はちょうど $n$ 個である
各ノードと接続されている頂点は根付き木において葉である
問題文中の図のようにグラフを図示するとき、辺が交差することはない

解法

先に与えられる頂点数 $a$ の根付き木を「根付き木A」、後に与えられる頂点数 $b$ の根付き木を「根付き木B」と呼ぶことにします。

各辺について、「その辺を取り除いたら、 $n$ 個のノードのうちどこからどれまでが根と分断されるか？」を求めます。グラフが交差しないという制約によりこれは必ず区間になり、その両端はDFS等で求めることができます。

そうすると根付き木Aの辺と根付き木Bの辺のペアについて、「これらを同時に取り除くことは可能か？」という判定ができます。具体的には先ほどの「根と分断されるノードの区間」が共通部分を持っていれば同時に取り除くことは不可能です。逆にそのようなペアを同時に取り除かない場合は問題の条件を満たします。

つまりこの問題は以下のように帰着できます。

あらかじめ全ての辺の本数だけ報酬をもらう。
それぞれの辺を取り除くか残すか選べて、残す場合は罰金1を支払う。
この辺とこの辺を同時に取り除いてはいけない（罰金 $\infty$ ）、という制約が存在する。
これらの条件で報酬を最大化、つまり罰金を最小化する。

あらかじめ全ての辺の本数だけ報酬をもらい、残す辺の本数だけ罰金を払うことで、差し引いて得られる報酬が「除去する辺の本数」に対応します。これを最大化するので答えが求まります。

これはいわゆる「燃やす埋める問題」として最小カット問題に落とし込むことができます。「同時に取り除くと罰金」という条件は普通は扱えないのですが、この制約は異なる根付き木の辺間にしかないので、以下の図のように始点側と終点側の対応を逆にすることで上手くいきます。

f:id:betrue12:20191201023902p:plain

全ての辺の本数から最小カット重みを引いたものが答えになります。

計算量の評価をすると、最小カットに帰着したグラフにおいて頂点数 $V = a+b$ 。辺数は $E = (a-1) + (b-1) + (同時に取り除けないペア数)$ ですが、同時に取り除けないペア数が $(a-1)(b-1) - n(n-1)$ であるケースは作れるのでおよそ300万くらいまでは増える可能性があります。Dinic法の最悪計算量が $O(V^{2}E)$ なので単純計算だと全然間に合ってませんが、Dinicは速いので通ります（？）