simezi_tan https://blog.hatena.ne.jp/simezi_tan/ simezi_tanの日記 https://simezi-tan.hatenadiary.org/ TopCoder フロー 問題 nxnのグリッドに白石'o'と黒石'x'が置かれている。 何も置かれていない場所は'.' 辺を共有する白石はひとかたまりとみなす。 ひとかたまりの白石が、何も置かれていない場所に隣接していない状態になると、 その白石は全て'.'に変わる。黒石を好きなだけ置くことができるとき、 グリッドの空いているマスの個数は最大いくつにできるか求めよ。 置かれている黒石や、置いた黒石はなくなることはない。 制約条件 n≦50 初期状態で、白石のかたまりは必ずどこかの'.'と隣接している。 方針 最小カット。 フローグラフを以下のように構成する。 'o'に対応する頂点：その頂点がs-tカットのs側に含まれ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsimezi-tan.hatenadiary.org%2Fentry%2F20131016%2F1381913292" title="TopCoder SRM 594 Div1 Medium FoxAndGo3 - simezi_tanの日記" 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 2013-10-16 17:48:12 rich https://simezi-tan.hatenadiary.org/entry/20131016/1381913292 1.0 100%