再帰的な構造の迷路。考察が結構面白いので解法は読まない方がいい。 はじめに 2018年11月18日に開催された XIX Open Cup named afer E.V. Pankratiev, Grand Prix of Siberia の問11「Recursive Circuit」の問題と解法を述べる。 Open Cup Open CupはICPCに…

Global Minimum Cut Stoer-Wagner algorithm 無向グラフに対して、あらゆるペア(s, t)のカットの中で最小の s-t-カットを求める。 問題 重み付無向グラフが与えられる。各頂点にSかTを割り当てたとき、一端がSでもう一端がTの辺の重みの総和をその「割り当て…