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

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

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

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

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

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

とこはるのまとめ