Area1 https://blog.hatena.ne.jp/Area1/ Area1のif(memo[i][j]) https://area.hateblo.jp/ SRM グラフ 深さ優先探索 問題 都市がいくつかあり、都市間の道の情報とその道を壊すコストが与えられる。任意の都市間で往来ができるように道路が敷かれており、そのパスは必ず1つだけである（要は閉路がない）。敵に征圧された街の番号が与えられるので、道路をいくつか壊して、征圧された都市同士で往来ができないようにしたい。道路を壊すコストを最小化せよ。 やりかた 単純な深さ優先探索で通る。ある征圧された都市から始めて、つながっている都市を見ていき、別の征圧された都市に辿り着いた時、そこまでの道路の中で最もコストの低い道路を壊す。壊した時点でその道路はもう使用できないフラグをたて、探索をいったんすべて打ち切る。そうするとこの2都市間… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Farea.hateblo.jp%2Fentry%2F2014%2F11%2F07%2F011643" title="SRM 328 Div1 Medium BlockEnemy - Area1のif(memo[i][j])" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/A/Area1/20141107/20141107010857.png Hatena Blog https://hatena.blog 2014-11-07 01:16:43 rich https://area.hateblo.jp/entry/2014/11/07/011643 1.0 100%