ek.cpp

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

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

const int N = 128;
const int INF = 1 << 28;

class Network {
private:
	int v, s, t;
	int cap[N][N], flow[N][N], prev[N];
	bool bfs();
public:
	int maxFlow(int, int);
};
bool Network::bfs() {
	queue<int> Q;
	bool vst[N] = { false };
	Q.push(s); vst[s] = true;
	while(!Q.empty()) {
		int u = Q.front(); Q.pop();
		for(int i = 0; i < v; i++)
			if(!vst[i] && cap[u][i] != flow[u][i]) {
				Q.push(i); prev[i] = u; vst[i] = true;
				if(i == t) return true;
			}
	}
	return false;
}
int Network::maxFlow(int ss, int tt) {
	s = ss; t = tt;
	memset(flow, 0, sizeof(flow));
	int f = 0;
	while(bfs()) {
		int ex = INF;
		for(int c = t; c != s; c = prev[c]) ex <?= cap[prev[c]][c]-flow[prev[c]][c];
		for(int c = t; c != s; c = prev[c]) 
			{ flow[prev[c]][c] += ex; flow[c][prev[c]] -= ex; }
		f += ex;
	}
	return f;
}