学步园

今天终于理解了KM顶标的作用， 贴一份O(n^3)的模板。

zkw_flow 跟顶标也有点关系，它是把距离dis数组当作顶标，之后在不断给图加可流边，跟把边加入KM相等子图的过程是几乎差不多的。

//****************KM 二分图求最大价值
//建图(当求最小值时建负权边)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 105;
const int inf = 1e9;
int n;
int match[maxn], t[maxn], s[maxn];
int w[maxn][maxn], lx[maxn], ly[maxn], slack[maxn];
bool path(int u) {
	int v;
	s[u] = true;
	for(v = 1; v <= n; v++)
		if(!t[v]) {
			int tmp = lx[u] + ly[v] - w[u][v];
			if(!tmp) {
				t[v] = true;
				if(match[v] == -1 || path(match[v])) {
					match[v] = u;
					return true;
				}
			}
			else slack[v] = min(slack[v], tmp);
		}
	return false;
}

void update() {
	int d = inf;
	int i;
	for(i = 1; i <= n; i++)
		if(!t[i]) d = min(d, slack[i]);
	for(i = 1; i <= n; i++) {
		if(s[i]) lx[i] -= d;
		if(t[i]) ly[i] += d;
		else slack[i] -= d;
	}
}

void km() {
	int i, j;
	for(i = 1; i <= n; i++) {
		match[i] = -1;
		ly[i] = 0;
		lx[i] = -inf;
		for(j = 1; j <= n; j++)
			lx[i] = max(lx[i], w[i][j]);
	}
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= n; j++)
			slack[j] = inf;
		while(true) {
			memset(s, false, sizeof(s));
			memset(t, false, sizeof(t));
			if(path(i)) break;
			else update();
		}
	}
}

zkw_flow

#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 210;
const int inf = 1e9;

struct zkw_flow {
	int s, t, n;
	int mincost, maxflow;
	struct Edge {
		int v, c, w, next;
	} edge[1000006];
	int head[maxn], E;
	void init() {
		memset(head, -1, sizeof(head));
		E = 0;
	}
	void add(int s, int t, int c, int w) {
		edge[E] = (Edge) {t, c, w, head[s]};
		head[s] = E++;
		edge[E] = (Edge) {s, 0, -w, head[t]};
		head[t] = E++;
	}
	int dis[maxn];
	bool vis[maxn];
	void spfa() {
		int i, u;
		for(i = 1; i <= n; ++i)
			dis[i] = inf, vis[i] = false;
		queue <int> q;
		dis[s] = 0, q.push(s), vis[s] = true;
		while(!q.empty()) {
			u = q.front(), q.pop(), vis[u] = 0;
			for(i = head[u]; ~i; i = edge[i].next) {
				int v = edge[i].v;
				if(edge[i].c && dis[v] > dis[u] + edge[i].w) {
					dis[v] = dis[u] + edge[i].w;
					if(!vis[v]) {
						vis[v] = true;
						q.push(v);
					}
				}
			}
		}
		for(int i = 1; i <= n; ++i)
			dis[i] = dis[t] - dis[i];
	}

	int aug(int u, int lim) {
		if(u == t) {
			maxflow += lim;
			mincost += dis[s] * lim;
			return lim;
		}
		vis[u] = true;
		int res = lim;
		for(int i = head[u]; ~i; i = edge[i].next) {
			int v = edge[i].v;
			if(edge[i].c && !vis[v] && dis[u] == dis[v] + edge[i].w) {
				int tmp = aug(v, min(lim, edge[i].c));
				edge[i].c -= tmp;
				edge[i ^ 1].c += tmp;
				lim -= tmp;
				if(!lim) break;
			}
		}
		return res-lim;
	}

	bool update() {
		int d = inf, i;
		for(int u = 1; u <= n; ++u)if(vis[u])
			for(i = head[u]; ~i; i = edge[i].next) {
				int v = edge[i].v;
				if(edge[i].c && !vis[v])
					d = min(d, dis[v] + edge[i].w - dis[u]);
			}
		if(d == inf) return false;
		for(int i = 1; i <= n; ++i)
			if(vis[i]) dis[i] += d;
		return true;
	}

	int mcmf(int s, int t, int n) {
		this->s = s, this->t = t, this->n = n;
		mincost = maxflow = 0;
		spfa();
		do {
			do {
				memset(vis, false, sizeof(vis));
			}while(aug(s, inf));
		}while(update());
		return mincost;
	}
} g;