燃やす埋める(Project Selection Problem)の練習問題についての解説です。
問題はこちら
ポイント
- 選択に対するコストからグラフを構築する
問題概要
からなる文字列が与えられます。円支払うことにより、を(ならばに、ならばに)変更することができます。また、個の区間が与えられ、文字列について円追加で支払う必要があります。- 文字列を回文にするために必要な文字の最小変更回数
例えば、を回文にするためには文字目を変更する必要があるためとなります。
適切にの文字を変更することにより、支払う金額を最小化してください。
解説
燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください.kanpurin.hatenablog.com
各を[変更しない/変更する]を選択肢とするのではなく、[0にする/1にする]を選択肢とします(が最終的なの値に関する制約なので)。
もともとであるのものは以下のコストがかかります。
であるのものも同様にして以下のコストがかかります。
の値はとなるようなの個数です。したがって、となる場合にのコストがかかると考えます。
グラフを作成していきます。各文字に対応する頂点を作り、始点Sから各頂点に向けて有向辺を張り、各頂点から終点Tに向けて有向辺を張ります。このグラフの(S,T)カットで頂点がS側の集合に含まれることを「をにする」ことに、T側の集合に含まれることを「をにする」ことに対応させます。上のコスト表を見ると、かのときにコストをかけたいです。にコストをかける場合、つまり頂点がS側に、頂点がT側にある際にコストをかける場合は頂点から頂点に重みの有向辺を張ればよいです。
入力例1に対するグラフは以下のようになります。重みの辺は省略しています。
同じ頂点対に辺を張る場合はをまとめて張ると辺の数はとなります。頂点数はとなるので、Dinicを用いると時間計算量、Push-Relabelを用いるとで解くことができます。
※2022/10/13追記
同じ頂点間に張られている辺はまとめて下さい.
にの辺が張られていたらの辺のみ張るようにする
他の燃やす埋める問題(Project Selection Problem)の例題については以下にまとめています。
kanpurin.hatenablog.com