匈牙利算法,又名相亲算法,还有一个名字叫抢老婆算法...
#include <iostream>
#include <string.h>
using namespace std;
const int N = 510;
int v[N],p[N],con[N][N];
int b,g,m;
bool match(int x)
{
for(int i = 1;i <= g;i ++)
{
if(!v[i]&&con[x][i])
{
v[i] = 1;
if(!p[i] || match(p[i]))
{
p[i] = x;
return true;
}
}
}
return false;
}
int Hungarian()
{
int res = 0;
for(int i = 1;i <= b;i ++)
{
memset(v,0,sizeof v);
if(match(i)) res ++;
}
return res;
}
int main()
{
cin >> b >> g >> m;
while(m --)
{
int x,y;
cin >> x >> y;
con[x][y] = 1;
}
cout << Hungarian();
}