とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

高速化できる最小費用流のよくあるからくり / グリッド上の最大流問題

この記事は Competitive Programming (1) Advent Calendar 2019 - Adventar の25日目の記事です.
24日目はbeet_aizuさんの記事で,Online Judge Verify Helper のススメ - beet's soilでした.

この記事ですが,気合を入れすぎたので15ページもあります.
その分,短い記事ではフォローすることが難しい概念を説明したつもりですので,お楽しみください.

イントロ

この記事は次のとおり,二部構成となっています.

前半は「普通に考えると最小費用流なのに$O(N)$や$O(N \log N)$程度の計算量を要求されてしまう...」という類の問題についてです.この問題へのアプローチと例題の解説をします.
紹介する問題 : JOI2018/2019 本選 問題4「コイン集め」

後半は「グリッド上の最大流」になります.左上から右下へ容量無限大の辺を無数に張られていて,ソースとシンクがたくさんあるような設定の最大流について扱います.
紹介する問題 : いろはちゃんコンテストDay4 F「道なき道を」, JOI2018/2019 春合宿 Day2 「ふたつの料理」

想定読者層は,最大流問題,最小費用流問題について,それぞれ問題を解いたことがあるのが最低ラインだと思います.(特に何の理由もつけずに,「この問題はナイーブなフローで解けますね~」,くらいの説明をすることになります)

本編

tokoharupage/advent2019.pdf at master · tokoharu/tokoharupage · GitHub
手元にダウンロードして読むのがよいかと思います

f:id:tokoharu-sakura:20191223221245p:plain
今回作って気に入った画像