hlpp.cpp

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

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

const int N = 256;
const int INF = 1 << 30;

class Edge {
public:
	int u, v, cuv, cvu, flow;
	Edge() {}
	Edge(int cu, int cv, int ccu, int ccv) : u(cu), v(cv), cuv(ccu), cvu(ccv), flow(0) {}
	int other(int p) const { return p == u ? v : u; }
	int cap(int p) const { return p == u ? cuv-flow : cvu+flow; }
	void addFlow(int p, int f) { flow += (p == u ? f : -f); }
};

class NodeList {
private:
	int level, next[N], index[2*N], v;
public:
	void clear(int cv) { v = cv; level = -1; memset(index, -1, sizeof(index)); }
	void insert(int n, int h) { next[n] = index[h]; index[h] = n; level >?= h; }
	int remove();
	bool empty() const { return level < 0; }
};
int NodeList::remove() {
	int r = index[level]; index[level] = next[index[level]];
	while(level >= 0 && index[level] == -1) level--;
	return r;
}

class Network {
private:
	vector<Edge> eg;
	vector<Edge*> net[N];
	int n, v, s, t;
	NodeList list;
	int h[N], hn[2*N], e[N], cur[N];
	void initNet();
	void initFlow();
	void initHeight();
	void push(int);
	void relabel(int);
	void discharge(int);
	void gapHeuristic(int);
public:
	int maxFlow(int, int);
};
void Network::gapHeuristic(int k) {
	if(hn[k] != 0 || k >= v+1) return;
	for(int i = 0; i < v; i++)
		if(h[i] > k && h[i] <= v && i != s)
			{ hn[h[i]]--; hn[v+1]++; h[i] = v+1; }
}
void Network::initNet() {
	for(int i = 0; i < v; i++) net[i].clear();
	for(int i = eg.size()-1; i >= 0; i--) {
		net[eg[i].u].push_back(&eg[i]);
		net[eg[i].v].push_back(&eg[i]);
	}
}
void Network::initHeight() {
	memset(h, 0, sizeof(h)); memset(hn, 0, sizeof(hn));
	memset(e, 0, sizeof(e)); e[s] = INF;
	for(int i = 0; i < v; i++) h[i] = v;
	queue<int> Q; Q.push(t); h[t] = 0;
	while(!Q.empty()) {
		int p = Q.front(); Q.pop();
		for(int i = net[p].size()-1; i >= 0; i--) {
			int u = net[p][i]->other(p), ec = net[p][i]->cap(u);
			if(ec != 0 && h[u] == v && u != s) { h[u] = h[p]+1; Q.push(u); }
		}
	}
	for(int i = 0; i < v; i++) hn[h[i]]++;
}
void Network::initFlow() {
	initNet(); initHeight();
	for(int i = 0; i < v; i++) cur[i] = net[i].size()-1;
	list.clear(v);
	for(; cur[s] >= 0; cur[s]--) push(s);
}
void Network::push(int u) {
	Edge* te = net[u][cur[u]];
	int ex = min(te->cap(u), e[u]), p = te->other(u);
	if(e[p] == 0 && p != t) list.insert(p, h[p]);
	te->addFlow(u, ex); e[u] -= ex; e[p] += ex;
}
void Network::relabel(int u) {
	int mh = 2*v, oh = h[u];
	for(int i = net[u].size()-1; i >= 0; i--) {
		int p = net[u][i]->other(u);
		if(net[u][i]->cap(u) != 0) mh <?= h[p]+1;
	}
	hn[h[u]]--; hn[mh]++; h[u] = mh; cur[u] = net[u].size()-1;
	gapHeuristic(oh);
}
void Network::discharge(int u) {
	while(e[u] > 0)
		if(cur[u] < 0) relabel(u);
		else if(net[u][cur[u]]->cap(u) > 0 && h[u] == h[net[u][cur[u]]->other(u)]+1) push(u);
		else cur[u]--;
}
int Network::maxFlow(int ss, int tt) {
	s = ss; t = tt; initFlow();
	while(!list.empty()) {
		int u = list.remove();
		discharge(u);
	}
	return e[t];
}