bipartite_matching.cpp

This is a small program for bipartite matching...

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 100
#define init(a,b) memset(a,b,sizeof(a))

int n,m,a,b,path,matchL[MAXN],matchR[MAXN];
bool edge[MAXN][MAXN];
bool seen[MAXN];

bool bpm(int v){
	for (int u=0;u<m;u++){
		if (edge[v][u]){
			if (seen[u]) continue;
			seen[u]=1;
			if (matchR[u]==-1 || bpm(matchR[v])){
				matchL[u]=v;
				matchR[v]=u;
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	scanf("%d",&n);//n=bird
	scanf("%d",&m);//m=cage
	scanf("%d",&path);
	init(edge,0);
	for (int i=0;i<path;i++){
		scanf("%d%d",&a,&b);
		edge[a][b]=1;
	}
	init(matchL,-1);init(matchR,-1);
	int cnt=0;
	for (int i=0;i<n;i++){
		init(seen,0);
		if (bpm(i)) cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}