POJ 2914: Minimum Cut

http://poj.org/problem?id=2914

これもフローとはまた違った話。

全域最小カット。Stoer–Wagnerを使う。

Stoer–Wagnerは
「点の集合からの辺のコストの合計が大きいもの点から取っていって、最後から二番目に取った点sと最後に取った点tの最小カットは
tから生えてる辺のコストの合計になる」
という定理に基づいている。

この証明はw(Av,v)<=w(Cv)をvの一つ前に取った点uについての仮定w(Au,u)<=w(Cu)から示し、帰納法を使う。
(ただしAvはvよりも前に取った点集合、Cvはs-tカットのうち(Av or v)の集合に含まれてる辺の合計、w(Av,v)はAvからvへの辺のコストの合計)
補集合を考えると仮定をうまく利用できる。

詳しくは↓を参照。
https://www.slideshare.net/hcpc_hokudai/flow-cut

int global_min_cut(vector<vector<int> > g) { //g: n*n matrix of graph. if no edge, the cost is zero
	int n = (int)g.size(), res = inf; 
	vector<int> redV(n); 
	rep(i, 0, n) redV[i] = i; 
	rer(rem, n + 1, 2) { //calc MA order 
		int u = 0, v = 0, cut = 0; 
		vector<int> w(rem,0); 
		rep(i, 0, rem){ 
			u = v; v = max_element(all(w)) - w.begin(); 
			cut = w[v]; w[v] = -1; 
			rep(p, 0, rem) {
				if(w[p] >= 0) w[p] += g[redV[v]][redV[p]]; 
			}
		}
		//merge graph 
		rep(i,0, rem) { 
			g[redV[u]][redV[i]] += g[redV[v]][redV[i]]; 
			g[redV[i]][redV[u]] += g[redV[i]][redV[v]]; 
		} 
		redV.erase(redV.begin() + v); 
		//update min_cut 
		res = min(res, cut);
	} 
	return res; 
}

int N, M;

int main() {
	while(scanf("%d%d", &N, &M) != EOF) {
		vector<vector<int> > g(N, vector<int>(N, 0));
		rep(i, 0, M) {
			int a, b, c; scanf("%d%d%d", &a, &b, &c);
			g[a][b] += c;
			g[b][a] += c;
		}
		printf("%d\n", global_min_cut(g));
	}
	return 0;
}

補集合を考えるのはフローに帰着する際の頻出テク臭いね。