ABC214 H - Collecting - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 頂点 ${M}$ 辺の有向グラフがあり， ${K}$ 人が ${1}$ 人ずつ頂点 ${1}$ から辺を辿って任意の回数繰り返す．人が ${1}$ 人以上通った頂点 ${v}$ の ${X_v}$ の値の総和の最大値を求めよ．

${2\leq N\leq 2×10^5\\ 1\leq M\leq 2×10^5\\ 1\leq K\leq 10\\ 1\leq X_i\leq 10^9}$

解説

ある強連結成分を通るときはその強連結成分の全頂点を通るべきなので強連結成分分解してDAGにする．以降はDAGで解く．
各頂点から新たに作った頂点 ${T}$ に有向辺を張る．このグラフにおける頂点 ${1}$ から頂点 ${T}$ への ${K}$ 本のパスに含まれる頂点の ${X_v}$ の和の最大値が答え．
問題が最小費用流っぽい．最大化だったり，頂点にコストがあったりするが実は最小費用流のアルゴリズムで解ける．

最大化を最小化にするために ${X_i}$ を ${-X_i}$ にする．負のコストをもつ辺ができるが，これは後で処理する．

頂点のコストは，頂点毎に以下のように頂点を2つ作る．この頂点を通るフローは必ず下図の2頂点の間の辺を通るのでこのように辺のコストに変換することができる．

f:id:kanpurin:20210815100618p:plain:w300

複数回頂点を通っても最初の ${1}$ 回しかコストが発生しない．これは上記の2頂点間に「容量 ${1}$ ，コスト ${-X_v}$ の辺」と「容量 ${\infty}$ (実装では ${K-1}$ でいい)，コスト ${0}$ の辺」を張ることで実現できる．優先的にコスト ${-X_v}$ の辺から使われるのでこの方法でよい．

こうしてできたグラフの頂点 ${1}$ から頂点 ${T}$ へ流量 ${K}$ を流すときの最小コストが答えとなるが，負のコストをもつ辺があるので非負コストの辺のみからなるグラフの最小費用流に言い換える必要がある．

snuke.hatenablog.com

辺に適切に定数を足す．
あらかじめ負のコストを持つ辺に最大までフローを流す．
最短距離を求めるアルゴリズムを用いてポテンシャルを初期化する(アリ本に説明アリ)．

1は公式解説の方法であり，問題ごとに考える必要がある(ライブラリ化難しそう？)．2は今回の問題だと全頂点に負のコストがあるので流すフローが多くなり間に合わない．3は負のコストがあるグラフの最短距離を求めるアルゴリズムであるBellman-Fordを用いると ${O(NM)}$ かかり間に合わないが，グラフがDAGであることを利用してトポロジカル順にDPすることで最短距離が ${O(N+M)}$ で求められる．

提出プログラム

https://atcoder.jp/contests/abc214/submissions/25067496

感想

Gより典型度高い．
最小費用流の負辺除去は1の方法でやろうとするとこんがらがる．