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

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>

using namespace std;

int m, n, sc;
bool a[1111][1111], vs[1111];
int x[1111], y[1111];

bool tim(int i) {
	if(vs[i]) return false;
	vs[i] = true;
	for(int j=1;j<=n;++j) if(a[i][j]) {
		if(y[j]==0) {
			x[i] = j;
			y[j] = i;
			return true;
		}
		if(tim(y[j])) {
			x[i] = j;
			y[j] = i;
			return true;
		}
	}
	return false;
}

int main() {
	int u, v, socap=0;
	scanf("%d%d%d", &m, &n, &sc);
	for(int i=0;i<sc;++i) {
		scanf("%d%d", &u, &v);
		a[u][v] = true;
	}
	for(int i=1;i<=m;++i) {
		memset( vs, 0, sizeof(vs));
		if(tim(i)) ++socap;
	}
	cout << socap << endl;
	//system("pause");
	return 0;
}

Download