maxmatch.cpp

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

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

const int N = 128;

class Graph {
private:
	bool map[N][N], check[N];
	int n, match[N];
	bool dfs(int);
public:
	int maxMatch();
};
bool Graph::dfs(int p) {
	for(int i = 0; i < n; i++) {
		if(!check[i] && map[p][i]) {
			check[i] = true;
			int t = match[i];
			match[i] = p;
			if(t == -1 || dfs(t))  return true;
			match[i] = t;
		}
	}
	return false;
}
int Graph::maxMatch() {
	memset(match, -1, sizeof(match));
	int mth = 0;
	for(int i = 0; i < n; i++) {
		memset(check, false, sizeof(check));
		if(dfs(i)) mth++;
	}
	return mth;
}