hungray.cpp

二分图匹配-匈牙利算法 效率很高

#include  <iostream>
//soj2737
const   int   MaxN = 500 + 1;
bool   map[MaxN][MaxN] , ck[MaxN];
int     n , match[MaxN] , max_match , k; 

void  Input()
{
      int i  , x , y;
      for ( i = 1 ; i <= k ; i++)
      {
              scanf("%d%d",&x,&y);
              map[x][y] = true;
      }      
}
bool  search(int x)
{
      int i , t;
      for (i = 1 ; i <= n ; i ++)
      if (map[i][x]&&!ck[i])
      {
          ck[i] = true;
          t = match[i];
          match[i] = x;
          if (t ==0 || search(t)) return true;
          match[i] = t;                           
      }
      return false;      
}
void  Main()
{
      int  i ;
      memset(match , 0 , sizeof(match));
      max_match = 0;
      for ( i = 1 ; i <= n ; i ++)
      {
         memset(ck , false , sizeof(ck));
         if (search(i)) max_match++;
      }      
}
void  Output()
{
      printf("%d\n",max_match);      
}
int   main()
{
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
      while( scanf("%d%d",&n,&k) == 2)
      {
         Input();
         Main();
         Output();
       }
      return 0;      
}