roottree.cpp

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

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

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

class Graph {
private:
	int n, m, w[N][N], prev[N], minc[N], base[N];
	void findArc(int);
	int findCir();
	void contract(int);
	void spray(int);
public:
	int rootTree(int);
};
void Graph::findArc(int u) {
	for(int i = 0; i < m; i++) 
		if(base[i] == i) minc[i] = INF;
	for(int i = 0; i < m; i++) {
		if(base[i] != i) continue;
		for(int j = 0; j < m; j++)
			if(base[j] == j && j != u && minc[j] > w[i][j])
				{ minc[j] = w[i][j]; prev[j] = i; }
	}
}
int Graph::findCir() {
	int vst[N]; memset(vst, -1, sizeof(vst));
	for(int i = 0; i < m; i++) {
		if(i != base[i] || vst[i] != -1) continue;
		vst[i] = i;
		for(int u = prev[i]; u != -1; u = prev[u])
			if(vst[u] == i) return u;
			else if(vst[u] != -1) break;
			else vst[u] = i;
	}
	return -1;
}
void Graph::contract(int u) {
	base[m] = base[u] = m;
	for(int i = prev[u]; i != u; i = prev[i]) base[i] = m;
	for(int i = 0; i <= m; i++) w[i][m] = w[m][i] = INF;
	for(int i = 0; i < m; i++) {
		if(base[i] != m) continue;
		for(int j = 0; j < m; j++) {
			if(base[j] != j || base[j] == m) continue;
			if(w[i][j] != INF) w[m][j] <?= w[i][j];
			if(w[j][i] != INF) w[j][m] <?= w[j][i]-minc[i];
		}
	}
}
void Graph::spray(int u) {
	bool pst = false;
	for(int i = 0; i < m; i++) {
		if(base[i] != u) continue;
		for(int v = 0; v < m; v++)
			if(prev[v] == u && w[i][v] == w[u][v]) prev[v] = i;
		if(!pst && w[prev[u]][u] == w[prev[u]][i]-minc[i]) { prev[i] = prev[u]; pst = true; }
	}
}
int Graph::rootTree(int u) {
	for(int i = 0; i < n; i++) base[i] = i;
	prev[u] = -1;
	for(m = n; true; m++) {
		findArc(u);
		for(int i = 0; i < m; i++)
			if(minc[i] == INF && i != u) return INF;
		int cn = findCir();
		if(cn == -1) break;
		else contract(cn);
	}
	for(; m > n; m--) spray(m-1);
	int cost = 0;
	for(int i = 0; i < n; i++)
		if(i != u) cost += w[prev[i]][i];
	return cost;
}