匹配:模板

0001-01-01
2分钟阅读时长

匹配:模板

UOJ78 二分图最大匹配(DFS - KM)

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 550;

int match[N], g[N][N], vis[N], link[N];
int n, m, e, tag, ans = 0;

bool dfs(int u) {
	
	for(int v=1; v<=m; ++v) {
		if(!g[u][v] or vis[v] == tag) continue;
		vis[v] = tag;
		if(!match[v] or dfs(match[v])) {
			match[v] = u;
			return true;
		}
	}
	return false;
}
int main() {
	
	scanf("%d%d%d", &n, &m, &e);
	for(int i=1, u, v; i<=e; ++i) {
		scanf("%d%d", &u, &v);
		g[u][v] = true;
	}
	
	for(int i=1; i<=n; ++i) {
		tag = i;
		if(dfs(i)) ++ans;
	}
	
	printf("%d\n", ans);
	for(int i=1; i<=m; ++i) link[match[i]] = i;
	
	for(int i=1; i<=n; ++i) printf("%d ", link[i]);
	
	return 0;
}

UOJ79 一般图最大匹配(带花树)

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 550;
int fa[N], match[N], pre[N], vis[N];
int tag = 0, n, m, ans = 0;
int flag[N];
bool g[N][N];
queue<int> q;

void clear(queue<int> &q) {
	queue<int> empty;
	swap(q, empty);
}
int belong(int u) {
	return fa[u] == u ? u : fa[u] = belong(fa[u]);
}

void path(int u) {
	while(u) {
		int v = match[pre[u]];
		match[u] = pre[u];
		match[pre[u]] = u;
		u = v;
	}
}
int lca(int u, int v) {
	++tag;
	u = belong(u);
	v = belong(v);
	while(vis[u] != tag) {
		vis[u] = tag;
		u = belong(pre[match[u]]);
		if(v) swap(u, v);
	}
	return u;
}
void connect(int u, int v, int root) {
	while(belong(u) != root) {
		pre[u] = v;
		v = match[u];
		if(flag[v] == 2) {
			q.push(v);
			flag[v] = 1;
		}
		if(belong(u) == u) fa[u] = root;
		if(belong(v) == v) fa[v] = root;
		u = pre[v];
	}
}
bool bfs(int u) {
	
	memset(flag, 0, sizeof flag);
	memset(pre, 0, sizeof pre);
	for(int i=1; i<=n; ++i) fa[i] = i;
	
	clear(q);
	q.push(u);
	flag[u] = 1;
	
	while(!q.empty()) {
		u = q.front();
		q.pop();
		for(int v=1; v<=n; ++v) {
			if(!g[u][v]) continue;
			if(flag[v] == 0) {
				pre[v] = u;
				if(match[v] == 0) {
					path(v);
					return true;
				}
				q.push(match[v]);
				flag[v] = 2;
				flag[match[v]] = 1;
			} else {
				if(flag[v] == 2) continue;
				if(belong(u) == belong(v)) continue;
				int root = lca(u, v);
				connect(u, v, root);
				connect(v, u, root);
			}
		}
	}
	return false;
}
int main() {
	
	scanf("%d%d", &n, &m);
	for(int i=1, u, v; i<=m; ++i) {
		scanf("%d%d", &u, &v);
		g[u][v] = g[v][u] = true;
	}
	
	for(int i=1; i<=n; ++i) 
		if(match[i] == 0 and bfs(i)) ++ans;
	
	printf("%d\n", ans);
	for(int i=1; i<=n; ++i) printf("%d ", match[i]);
	 
	return 0;
}

UOJ80 二分图最大权匹配(BFS - KM)

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 440;
const LL INF = 0x3f3f3f3f3f3f3f3f;

bool vis[N];
int pre[N], link[N], res[N];
int n, m, e;
LL g[N][N], lx[N], ly[N], d[N], ans = 0;

void bfs(int k) {
	
	int x, y = 0;
	LL min1 = INF, delta;
	memset(vis, false, sizeof vis);
	memset(pre, 0, sizeof pre);
	memset(d, 0x3f, sizeof d);
	link[y] = k;
	
	do {
		x = link[y], delta = INF, vis[y] = true;
		for(int i=1; i<=m; ++i) {
			if(!vis[i]) {
				if(d[i] > lx[x] + ly[i] - g[x][i]) {
					d[i] = lx[x] + ly[i] - g[x][i];
					pre[i] = y;
				}
				if(delta > d[i]) delta = d[i], min1 = i;
            }
        }
        for(int i=0; i<=m; ++i)
        	if(vis[i]) lx[link[i]] -= delta, ly[i] += delta;
        	else d[i] -= delta;
        y = min1;
    } while(link[y]);
    while(y) link[y] = link[pre[y]], y = pre[y];
}

int main() {
	
	scanf("%d%d%d", &n, &m, &e);
	m = max(n, m);
	for(int i=1; i<=e; ++i) {
		int u, v; LL w;
		scanf("%d%d%lld", &u, &v, &w);
		g[u][v] = w;
		lx[u] = max(lx[u], w);
	}
	
	for(int i=1; i<=n; ++i) bfs(i);
	
	for(int i=1; i<=m; ++i) {
		if(!g[link[i]][i]) continue;
		ans += g[link[i]][i];
		res[link[i]] = i;
	}
	printf("%lld\n", ans);
	for(int i=1; i<=n; ++i) printf("%d ", res[i]);
	
	return 0;
}
下一页 单调队列