用匈牙利算法求二分图的最大婚配

用匈牙利算法求二分图的最大匹配
1，  用匈牙利算法求二分图的最大匹配


算法轮廓：
(1)置M为空
(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
(3)重复(2)操作直到找不出增广路径为止
程序文件夹：22222


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


 const   int  MAXN  =   100 ;
 int  uN, vN;   // u,ｖ数目  
 bool  g[MAXN][MAXN]; // g[i][j] 表示 xi与yj相连  
 int  xM[MAXN], yM[MAXN];  //  输出量  
 bool  chk[MAXN];  // 辅助量 检查某轮 y[v]是否被check  
 
 
 
 bool  SearchPath( int  u)
  {
     int  v;
     for  (v = 0 ; v < vN; v ++ )
      {
         if  (g[u][v]  &&   ! chk[v])
          {
            chk[v]  =   true ;
             if  (yM[v]  ==   - 1   ||  SearchPath(yM[v])) 
              {
                yM[v]  =  u;
                xM[u]  =  v;
                 return   true ;
            } 
        } 
    } 
     return   false ;
} 
 
 
 int  MaxMatch()
  {
     int  u;
     int  ret  =   0 ;
    memset(xM,  - 1 ,  sizeof (xM));
    memset(yM,  - 1 ,  sizeof (yM));
     for  (u = 0 ; u < uN; u ++ )
      {
         if  (xM[u]  ==   - 1 )
          {
            memset(chk,  false ,  sizeof (chk));//Sets buffers to a specified character.


             if  (SearchPath(u)) ret ++ ;
        } 
    } 
     return  ret;
} 
 
 int  main()
  {
     int  i, k; 
     int  tU, tV;
   // ifstream cin( " test.txt " );
    cin  >>  uN  >>  vN  >>  k;
    memset(g,  false ,  sizeof (g));
     for  (i = 0 ; i < k; i ++ )
      {
        cin  >>  tU  >>  tV;
        g[tU][tV]  =   true ;
    }  
     int  M  =   MaxMatch();
    cout  <<   " Total Match:  "   <<  M  <<  endl;
     for  (i = 0 ; i < MAXN; i ++ )
         if  (xM[i]  !=   - 1 )
            cout  <<  i  <<   '   '   <<  xM[i]  <<  endl;
   system( " pause " );
    
     return   0 ; 
}  




 /**/ /* **********
test data:
    3 3 3
    1 1
    1 0
    2 2
********** */