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;
}

Download