FMATCH - Fast Maximum Matching

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<bits/stdc++.h>
using namespace std;

const int N = 50000, INF = 1e9;
int mx[N], my[N], d[N], nx, ny;
vector<int> g[N];

void enter() {
	int m; cin >> nx >> ny >> m;
	for(int i = 0; i < m; ++i) {
		int u, v; cin >> u >> v;
		g[u-1].push_back(v-1);
	}
}

bool dfs(int u, int mind) {
    for (int v : g[u]) if(my[v] == -1 ? d[u] == mind : d[my[v]] == d[u]+1 && dfs(my[v], mind)) return mx[u] = v, my[v] = u, true;
	d[u] = INF;
	return false;
}

int maxMatch() {
	int matching = 0;
    fill(mx, mx + nx, -1); fill(my, my + ny, -1);
	while(true) {
        fill(d, d + nx, INF); queue<int> q;
		for(int u = 0; u < nx; ++u) if(mx[u] == -1) d[u] = 0, q.push(u);
		int mind = INF;
		while(!q.empty()) {
			int u = q.front(); q.pop();
            for (int v : g[u]) if(my[v] == -1) mind = min(mind, d[u]);
			else if(d[my[v]] == INF) d[my[v]] = d[u]+1, q.push(my[v]);
		}
		if(mind == INF) break;
		for(int u = 0; u < nx; ++u) if(d[u] > mind) d[u] = INF;
		for(int u = 0; u < nx; ++u)
			if(mx[u] == -1 && dfs(u, mind)) ++matching;
	}
	return matching;
}

int main() {
	ios::sync_with_stdio(false);
	enter();
	cout << maxMatch() << endl;
	return 0;
}

Download