anta1 https://blog.hatena.ne.jp/anta1/ antaの競技プログラミング練習日記 https://anta1.hatenadiary.org/ SRM 最小費用流 問題 Editorial 問題 H*Wのマップlevelがある。マップの各セルには数字が書いてある。 左上(0, 0)から右下(W-1, H-1)へ、右か下のセルを辿っていく動きができる。このとき、たどったセルの数字がスコアに加算される。 3回上記の動きをするとき、得られるスコアを最大化せよ。 ただし、一回行ったセルにもう一度行ってもスコアは得られない 2 '0' level[0][0] = '0' 解答 最小費用流した。 各セルを2つA,Bに分ける。そして以下のようにエッジを張る。 A(x, y) → A(x+1, y), A(x, y+1) 容量 = ∞, 費用 = 0 A(x, y) →… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fanta1.hatenadiary.org%2Fentry%2F20121213%2F1355387098" title="SRM 208 DIV1 Hard StarAdventure - antaの競技プログラミング練習日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-12-13 17:24:58 rich https://anta1.hatenadiary.org/entry/20121213/1355387098 1.0 100%