早稲田大学プログラミングコンテスト2019 F - RPG
解法
「全ての頂点に対し、頂点 からのパスと、頂点
へ向かうパスが存在する」「閉路がない」という制約から、無駄な辺/頂点はないということが分かります。具体的には全ての
パスを考えた時、全ての辺/頂点についてそれを通る
パスが存在し、さらに任意の頂点間の全てのパスについてもそれを通る
パスが存在します。
そのため、問題は以下のように言い換えられます。
- 「戦闘頂点から戦闘頂点への任意のパスについて、そのパスに1つ以上の休憩所が存在する」という条件を満たすための最小コストを求めよ。
この問題は最小カット問題として解くことが出来ます。全ての戦闘頂点の「出口」を始点側に置き、「入口」を終点側に置きます。その間に他の頂点や辺を置き、休憩所を置くという操作を辺を切るという操作に上手く対応付けることができれば、最小カットコストがこの問題の答えに対応付けられます。
今回の場合は頂点がコストを持っているため、元のグラフにおける頂点を2つの頂点に分けてその間にコストを持つ辺を置くという方法が有効です。
具体的に入力例1を最小カット問題に帰着させたグラフは以下のようになります。
このグラフの 最小カットを求めることで、答えを求めることが出来ます。
