NKBM - Cặp ghép cực đại trên đồ thị hai phía

Tác giả: happyboy99x

Ngôn ngữ: C++

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

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
#define mset(a,i) memset(a, i, sizeof a)
const int N = 1000;
int nx, ny, my[N], vy[N];
vector<int> g[N];

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

bool dfs(int s) {
	TR(g[s], u) if(!vy[*u]) {
		vy[*u] = true;
		if(my[*u] == -1 || dfs(my[*u])) return my[*u] = s, true;
	}
	return false;
}

int maxMatch() {
	mset(my, -1); int res = 0;
	for(int i = 0; mset(vy, 0), i < nx; ++i) if(dfs(i)) ++res;
	return res;
}

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

Download