bitpartite.cpp

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

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
const int N = 40960;
const int INF = 1 << 28;

class Graph {
private:
	vector<int> g[N];
	int ns, nt, xmate[N], ymate[N], ds[N], dt[N], dis;
	bool vst[N];
	bool search();
	bool dfs(int);
public:
	int match();
};
bool Graph::search() {
	memset(ds, -1, sizeof(ds)); memset(dt, -1, sizeof(dt));
	queue<int> Q; dis = INF;
	for(int i = 0; i < ns; i++)
		if(xmate[i] == -1) { Q.push(i); ds[i] = 0; }
	while(!Q.empty()) {
		int u = Q.front(); Q.pop();
		if(ds[u] > dis) break;
		for(int i = g[u].size()-1; i >= 0; i--) {
			int v = g[u][i];
			if(dt[v] != -1) continue;
			dt[v] = ds[u]+1;
			if(ymate[v] == -1) dis = dt[v];
			else { ds[ymate[v]] = dt[v]+1; Q.push(ymate[v]); }
		}
	}
	return (dis != INF);
}
bool Graph::dfs(int u) {
	for(int i = g[u].size()-1; i >= 0; i--) {
		int v = g[u][i];
		if(vst[v] || dt[v] != ds[u]+1) continue;
		int ut = ymate[v], vs = xmate[u];
		vst[v] = true;
		if(ut != -1 && dt[v] == dis) continue;
		ymate[v] = u; xmate[u] = v;
		if(ut == -1 || dfs(ut)) return true;
		ymate[v] = ut; xmate[u] = vs;
	}
	return false;
}
int Graph::match() {
	int mth = 0;
	memset(xmate, -1, sizeof(xmate)); memset(ymate, -1, sizeof(ymate));
	while(search()) {
		memset(vst, false, sizeof(vst));
		for(int i = 0; i < ns; i++)
			if(ds[i] == 0 && dfs(i)) mth++;
	}
	return mth;
}