yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ Nagamochi-Ibaraki考案らしいです。 はじめに この記事は無向グラフの最小カット、つまり無向グラフを2つに分断する時、切らなくてはならない道の本数の最小を高速に求めるアルゴリズムの解説をします。 アルゴリズムへの下準備 最大隣接順序 f(x, y)をxとyの間に張っている道の本数と定義します。 最初に、最大隣接順序というものを定義します。 最大隣接順序とは、まず好きな頂点を１つ選び、v_1とします。 次に、v_1と最も多い本数の道で繋がっている頂点をv_2とします。 つまり、v_1とv_2以外の任意の頂点mについて f(v_1, v_2) ≧ f(v1, m)が成立します。 次に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2014%2F02%2F07%2F011122" title="無向グラフの最小カットを求めるアルゴリズム - よすぽの日記" 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 2014-02-07 01:11:22 rich https://yosupo.hatenablog.com/entry/2014/02/07/011122 1.0 100%