mincut.cpp

C++语言下, 关于图论算法的一些模版, 包括一般图最大匹配, km匹配, 最小割等等, 共15个模版

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 512;
const int INF = 1 << 29;

class Graph {
private:
	int n, m, g[N][N];
	void mergeVertex(int, int);
public:
	int minCut();
};
void Graph::mergeVertex(int a, int b) {
	for(int i = 0; i < n; i++) { g[i][a] += g[i][b]; g[a][i] += g[b][i]; }
	for(int i = 0; i < n; i++) { g[i][b] = g[i][n-1]; g[b][i] = g[n-1][i]; }
	g[a][a] = 0; n--;
}
int Graph::minCut() {
	int cut = INF, d[N], w[N];
	bool seta[N];
	while(n != 1) {
		memset(seta, false, sizeof(seta)); memset(w, 0, sizeof(w));
		for(int i = 0; i < n; i++) {
			int mw = -INF, mi;
			for(int j = 0; j < n; j++)
				if(!seta[j] && mw < w[j]) { mw = w[j]; mi = j; }
			d[i] = mi; seta[mi] = true;
			for(int j = 0; j < n; j++)
				if(!seta[j]) w[j] += g[mi][j];
		}
		cut <?= w[d[n-1]];
		mergeVertex(d[n-2], d[n-1]);
	}
	return cut;
}