Lowlink

POJ 3713: Transferring Sylla

Mengerの定理より全域最小点カットを求めれば良い。すべての点対に対してフローを流せばできるが、それではTLE。 全域最小辺カットならO(V^3)のアルゴリズム(Stoer-Wagner)が存在するが、全域最小点カットは見つけられなかった。全域最小点カットが2以上にな…