ssp.cpp

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 128;
const int INF = 1 << 28;
 
class Edge {
public:
	int u, v, cuv, cvu, flow, cost;
	Edge(int cu, int cv, int ccu, int ccv, int cc) 
		: u(cu), v(cv), cuv(ccu), cvu(ccv), flow(0), cost(cc) {}
	int other(int p) const { return p == u ? v : u; }
	int cap(int p) const { return p == u ? cuv-flow : cvu+flow; }
	int ecost(int) const;
	void addFlow(int p, int f) { flow += (p == u ? f : -f); }
};
int Edge::ecost(int p) const {
	if(flow == 0) return cost;
	else if(flow > 0) return p == u ? cost : -cost;
	else return p == u ? -cost : cost;
}
 
class Network {
private:
	vector<Edge> eg;
	vector<Edge*> net[N];
	Edge *prev[N];
	int v, s, t;
	int flow, cost, phi[N], dis[N], pre[N];
	void initNet();
	void initFlow();
	bool dijkstra();
public:
	int getCost() const { return cost; }
	int getFlow() const { return flow; }
	int mincost(int, int);
};
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::initFlow() {
	flow = cost = 0;
	memset(phi, 0, sizeof(phi));
	initNet();
}
bool Network::dijkstra() {
	for(int i = 0; i < v; i++) dis[i] = INF;
	dis[s] = 0; prev[s] = NULL; pre[s] = -1;
	bool vst[N] = { false };
	for(int i = 1; i < v; i++) {
		int md = INF, u;
		for(int j = 0; j < v; j++)
			if(!vst[j] && md > dis[j]) { md = dis[j]; u = j; }
		if(md == INF) break;
		vst[u] = true;
		for(int j = net[u].size()-1; j >= 0; j--) {
			Edge *ce = net[u][j];
			if(ce->cap(u) > 0) {
				int p = ce->other(u), cw = ce->ecost(u)-phi[u]+phi[p];
				if(dis[p] > dis[u]+cw) { dis[p] = dis[u]+cw; prev[p] = ce; pre[p] = u; }
			}
		}
	}
	return (dis[t] != INF);
}
int Network::mincost(int ss, int tt) {
	s = ss; t = tt; initFlow();
	while(dijkstra()) {
		int ex = INF;
		for(int c = t; c != s; c = pre[c]) ex <?= prev[c]->cap(pre[c]);
		for(int c = t; c != s; c = pre[c]) prev[c]->addFlow(pre[c], ex);
		flow += ex; cost += ex*(dis[t]-phi[t]);
		for(int i = 0; i < v; i++) phi[i] -= dis[i];
	}
	return cost;
}