全域最小カット (Stoer-Wagner algorithm)

グラフ

Global Minimum Cut
Stoer-Wagner algorithm
無向グラフに対して、あらゆるペア(s, t)のカットの中で最小の s-t-カットを求める。

問題

重み付無向グラフが与えられる。各頂点にSかTを割り当てたとき、一端がSでもう一端がTの辺の重みの総和をその「割り当ての重み」とする。割り当ての重みの最小値を求めよ。

SとTはそれぞれ少なくとも1つ以上の頂点に割り当てなければならない。
重み 0以上
多重辺、自己ループあり
非連結あり

Stoer-Wagner algorithm

MinCutPhaseを実行すると、ある(s, t)に対して最小s-t-カットを求めることが出きる（ここがすごい）。
これがGlobalMinCutかもしれない、そうでない場合のために、s, tをマージしたグラフでも再びMinCutPhaseを実行する。

MinCutPhase

適当な1頂点aから始める。S-T-カットのS側は頂点aのみ、T側は残りの全ての頂点。
「最も重み合計の大きい頂点」を順番にS側に移動していく。T側に1頂点残った時に、「S側に最後に追加した頂点s」と「T側に最後に残った頂点t」について最小 s-t-カットになっている。
s-tについては最小だがglobal min cutとは限らない。どのs, tが残るのかはよくわからない。

計算量

隣接行列を用いた実装だとO(n^3)
隣接リスト + ヒープ O(n m log m)
隣接リスト + increase-keyを実装したヒープ O(n m + n^2 log n)

参考までに、s=1と固定してtをそれ以外の頂点全て試してDinic法 O(n^2 m) を実行して最小カットを求める場合、O(n^3 m)。

参考

Stoer–Wagner algorithm - Wikipedia (C++実装)
Spaghetti Source - 無向グラフの全域最小カット (Nagamochi-Ibaraki/Stoer-Wagner) (C++実装)
全域最小カット (Stoer-Wagner Algorithm) - yaketake08's 実装メモ (Python実装、ヒープ実装)

オンラインジャッジ

コード

O(n^3)

const int MAXN = 511;
using Weight = long long;

int n;
Weight adj[MAXN][MAXN];
Weight cost[MAXN];
bool used[MAXN];
bool added[MAXN];
int group[MAXN];

Weight best_weight; // global mimum cut;
// cut[v] == ('S' or 'T');
char cut[MAXN+1];

void init(int n_) {
    assert(2 <= n_ && n_ <= MAXN);
    n = n_;
    REP (i, n) memset(adj[i], 0, sizeof (Weight) * n);
}

// add undirected edge;
void add_edge(int x, int y, Weight weight) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    assert(weight >= 0);

    adj[x][y] += weight;
    adj[y][x] += weight;
}

// find global minimum cut;
Weight solve() {
    memset(used, 0, sizeof (bool) * n);
    REP (i, n) group[i] = i;
    cut[n] = 0;
    best_weight = -1;

    for (int phase=n-1; phase>=0; phase--) {
	memcpy(cost, adj[0], sizeof (Weight) * n);
	memcpy(added, used, sizeof (bool) * n);
	int prev, last = 0;
	REP (i, phase) {
	    prev = last;
	    last = -1;
	    // last: the most tightly connected vertex;
	    for (int j=1; j<n; j++) {
		if (!added[j] && (last == -1 || cost[j] > cost[last])) last = j;
	    }
	    if (i == phase - 1) {
		if (best_weight == -1 || cost[last] < best_weight) {
		    // (prev, last)-cut;
		    best_weight = cost[last];
		    // update mimimum cut;
		    REP (j, n) cut[j] = (group[j] == last? 'T': 'S');
		}
		REP (j, n) adj[prev][j] += adj[last][j]; // merge;
		REP (j, n) adj[j][prev] = adj[prev][j]; // copy edge cost;
		used[last] = true;
		REP (j, n) if (group[j] == last) group[j] = prev;
	    } else {
		REP (j, n) cost[j] += adj[last][j];
		added[last] = true;
	    }
	}
    }

    return best_weight;
}

使い方

UVa 10989。

void MAIN() {
    int N, M;
    scanf("%d%d", &N, &M);
    init(N);
    REP (i, M) {
	int x, y, c;
	scanf("%d%d%d", &x, &y, &c);
	x--; y--;
	add_edge(x, y, c);
    }
    LL ans = solve();
    printf("%lld\n", ans);
}

またcutの頂点集合も求めている。cut[i] == 'S' ならばS側、cut[i] == 'T' ならT側。