karpmincir.cpp

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

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

const int N = 680;
const int INF = 1 << 20;

class Graph {
private:
	int n, d[N][N], kd[N][N];
	int g[N][N], gn[N];
	int order(char, char);
public:
	double karp();
};
double Graph::karp()
{
	for(int i = 0; i <= n; i++)
		for(int j = 0; j < n; j++)
			kd[i][j] = INF;
	kd[0][0] = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < n; j++)
			if(kd[i-1][j] == INF) continue;
			else for(int k = gn[j]-1; k >= 0; k--)
				kd[i][g[j][k]] <?= kd[i-1][j]+d[j][g[j][k]];
	double minc = 1e20; bool est = false;
	for(int i = 1; i < n; i++) {
		double mc = -1e20;
		if(kd[n][i] == INF) continue;
		for(int j = 0; j < n; j++)
			if(kd[j][i] != INF) { mc >?= 1.0*(kd[n][i]-kd[j][i])/(n-j); est = true; }
		minc <?= mc;
	}
	if(!est) minc = 1e50;
	return minc;
}