二分图匹配-匈牙利算法实现

这是基于匈牙利算法的一个实现，相比基于网络流的方法要简单一些。

// 匈牙利算法求二分图的最大匹配
// billjeff
// Aug/29/2007

#include
using namespace std ;

#define FORI(n) for ( int i = 1 ; i <= n ; ++i )
#define FORJ(n) for ( int j = 1 ; j <= n ; ++j )

#define debug_over
#define file_io_no

class Graph {
private:
  static const int MAXNODE = 100 ;
  bool _xUsed[MAXNODE], _yUsed[MAXNODE], _xInRoute[MAXNODE], _yInRoute[MAXNODE] ;
  int _edge[MAXNODE][MAXNODE] ;
  int _x[MAXNODE], _y[MAXNODE] ;
  int _nodeNum, _xNum, _yNum ;
protected:
  bool find( int p ){
    #ifdef debug
    cout << "p = " << p << endl ;
    #endif
    int x = _x[p] ;
    _xInRoute[p] = true ;

    FORI(_yNum){
      int y = _y[i] ;
      if ( _edge[x][y] != -1 || _edge[y][x] != -1 )
      if ( !_yUsed[i] ){
        _edge[x][y] = _edge[y][x] = 1 ; //used ;
        _yUsed[i] = true ;
        _yInRoute[i] = true ;
        return true ;
      }
      else{
        int px = -1 ;
        FORJ(_xNum)
          if ( _edge[y][_x[j]] == 1 && !_xInRoute[j] ){
            px = j ;
            break ;
          }
        if ( px == -1 ) continue ;
        if ( find(px) ){
          _edge[x][y] = _edge[y][x] = 1 ;
          _edge[_x[px]][y] = _edge[y][_x[px]] = 1 ;
          return true ;
        }
      }     
    }
    return false ;
  }
public:
  /*
  Graph() : MAXNODE(100) {
  }
  */
  void readGraph(){
    cout << "Enter the number of nodes: " ;
    cin >> _nodeNum ;
    FORI(_nodeNum)
      FORJ(_nodeNum)
      _edge[i][j] = -1 ; // unconnected;   
    cout << "Enter the number of node in x side: " ;
    cin >> _xNum ;
    cout << "Enter the nodes of x side: " ;
    FORI(_xNum)  cin >> _x[i] ;
    cout << "Enter the number of node in y side: " ;
    cin >> _yNum ;
    cout << "Enter the nodes of y side: " ;
    FORI(_yNum)  cin >> _y[i] ;
    cout << "Enter the number of edges: " ;
    int n ;
    cin >> n ;   
    FORI(n){
      int x, y ;
      int s ;
      cin >> x >> y >> s ;    // s=0 indicate x<->y is connected; 
      _edge[x][y] = _edge[y][x] = s ;
    }
#ifdef debug
    cout << "x num: " << _xNum << "; y num: " << _yNum << "\n" ;
    FORI(_xNum)
      cout << _x[i] << " " ;
    cout << "\n" ;
    FORI(_yNum)
      cout << _y[i] << " " ;
    cout << endl ;
#endif
    return ;
  }
  void process(){
    FORI(_xNum)
      _xUsed[i] = false ;
    FORI(_yNum)
      _yUsed[i] = false ;
    bool flag = true ;
    while(flag){
      flag = false ;
      FORI(_xNum) _xInRoute[i] = false ;
      FORI(_yNum) _yInRoute[i] = false ;
      FORI(_xNum){
        #ifdef debug
        cout << "Here" << endl ;
        #endif
        if ( !_xUsed[i] ){           
          flag = find(i) ;
        }
        if ( flag ){
          _xUsed[i] = true ;
          break ;
        }
      }
    }
  }
  void print(){
    cout << "The mapping is: " << "\n" ;
    bool flag = false ;
    FORI(_xNum)
      FORJ(_yNum)
        if ( _edge[_x[i]][_y[j]] == 1 ){
          cout << _x[i] << "->" << _y[j] << "\n" ;
          flag = true ;
        }
    if ( !flag ) cout << "No Match is found!" << "\n" ;
    cout << endl ;
    return ;
  }
} ;


int main( void ){
  #ifdef file_io
  freopen( "out.txt", "w", stdout ) ;
  #endif
  Graph g ;
  g.readGraph() ;
  g.process() ;
  g.print() ;
  //system( "pause" ) ;
  return 0 ;
}