NKBM - Cặp ghép cực đại trên đồ thị hai phía
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
using namespace std;
int m,n,a[1111],b[1111],d[1111],c[1111][1111],t;
int dfs(int x)
{
int i;
fr(i,1,n)
if (c[x][i] && !d[i])
{
t=i; d[i]=x;
if (!b[i] || dfs(b[i])) return 1;
}
return 0;
}
int find()
{
int i;
fr(i,1,n) d[i]=0;
fr(i,1,m)
if (!a[i])
if (dfs(i)) return 1;
return 0;
}
void inc()
{
int x,y;
while (t)
{
x=d[t]; y=t;
t=a[x]; a[x]=y; b[y]=x;
}
}
int main()
{
int i,x,y,k,re=0;
cin >> m >> n >> k;
while (k--)
{
scanf("%d%d",&x,&y);
c[x][y]=1;
}
while (find()) inc();
fr(i,1,m)
if (a[i]) re++;
cout << re << endl;
return 0;
}