TDPC R - グラフ

• 問題
• AC

有向グラフに2つのパス（ウォーク？）を描いて、できるだけ多くの頂点を被覆する問題。流量2のフローを流す最小費用流問題に帰着する。

ネットワークの作り方を考える。まず、コスト（利得）を与えたいのは頂点なので、すべての頂点$v$を$v_{\operatorname{in}}$と$v_{\operatorname{out}}$に分割する。始点$S$から各$v_{\operatorname{in}}$​に容量$+\infty$・コスト$0$の辺を張り、$v_{\operatorname{out}}$から終点$T$にも容量$+\infty$・コスト$0$の辺を張る。また、元のグラフに頂点$u$から$v$への辺が存在するならば、$u_{\operatorname{out}}$から$v_{\operatorname{in}}$​へ容量$+\infty$・コスト$0$の辺を張る。

問題になるのは頂点へのコストの与え方で、1つのパスが頂点$v$を通ったら$1$の利得（=$−1$のコスト）になるが、もう1つのパスが同じ頂点を通っても利得はない、という条件を再現しなければならない。これは、$v_{\operatorname{in}}$​から$v_{\operatorname{out}}$​に2つの辺を張ることで実現する。1つの辺は容量$1$・コスト$−1$とし、もう1つは容量$+\infty$・コスト$0$とすればよい。

これでネットワークが完成したので、$S \rightarrow T$に流量$2$のフローを流して最小コストを求めればよい……が、最小費用流のアルゴリズムによっては負閉路をどうするかが問題になる。一番簡単なのは、最初にグラフを強連結成分分解して閉路をすべて1点に潰してしまい、できあがったDAG上で最小費用流を考えることだろう。この時、作るネットワークは上とほとんど変わらないが、頂点をまとめてしまっているので、$v_{\operatorname{in}}$​から$v_{\operatorname{out}}$へ張る辺のコストは変える必要がある: 一方の辺は容量$+\infty$・コスト$0$のままで良く、もう一方は容量$1$でコストを$−(元のグラフでvに対応する強連結成分のサイズ)$とする。

---

drkenさんのリストにフローの問題として挙がっていたのだが、自分では辺の張り方がわからなかった。上の方針はyosupoさんの提出に基づいている。