D. Wang's Log

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://billjeff.blogbus.com/logs/8010584.html

同样基于网络流算法进行处理的。源代码如下

// Maximum Binary-Mapping
// billjeff
// Aug/30/2007

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

#define debug_over

class BinGraph {
private:
  const static int MAXNODE = 100 ;
  bool _g[MAXNODE][MAXNODE] ; // Original graph info
  int _nodeNum ;
  int _currVol[MAXNODE][MAXNODE] ; // Current graph's volumn
  int _nodePrev[MAXNODE] ;
  int _xNode[MAXNODE], _yNode[MAXNODE] ;
  int _xNum, _yNum ;
protected:
  int check( int *arr ){
    int currNodeNum = _nodeNum+1 ;
    for ( int i = 0 ; i <= currNodeNum ; ++i )
      if ( arr[i] == 1 )
    return i ;
    return -1 ;
  }

  bool ford( int& a ){ // start point is 0, end point is _nodeNum+1 ;
    int currNodeNum = _nodeNum+1 ;
    int status[currNodeNum+1] ;   
    status[0] = 1 ; // labeled node - point 0 ;
    for ( int i = 1 ; i <= currNodeNum ; ++i )
      status[i] = 0 ; // unlabeled ;
    int nextNode ;
    while ( (nextNode = check(status)) != currNodeNum ) { // nextNode is not the terminal node
#ifdef debug
      cout << nextNode << endl ;
#endif
      if ( nextNode == -1 ){
    //cout << "Error" << endl ;
    return false ;
      }
      for ( int i = 1 ; i <= currNodeNum ; ++i )
    if ( status[i] == 0 && (_g[nextNode][i] || _g[i][nextNode]) ){
      if ( _g[nextNode][i] && _currVol[nextNode][i] == 0 ) {
        status[i] = 1 ; //labeled ;
        _nodePrev[i] = nextNode ;
      }
      else if ( _g[i][nextNode] && _currVol[i][nextNode] > 0 ){
        status[i] = 1 ;
        _nodePrev[i] = -nextNode ;
      }
    }
      status[nextNode] = 2 ; // checked ;
    }
    a = numeric_limits<int>::max() ;
    int p = currNodeNum ;
    while ( p != 0 ){
      int tp = _nodePrev[p] ;
      if ( tp < 0 ){ // p->tp
    tp = -tp ;
    a = (a>_currVol[p][tp])?_currVol[p][tp]:a ;
      }
      else
    { // tp->p
      int t = 1 - _currVol[tp][p] ;
      a = (a>t)?t:a ;
    }
      p = tp ;
    }
    if ( a > 0 )
      return true ;
    return false ;
  }

  void fulkerson( int v ){
    int p = _nodeNum+1 ;
    int tp ;
    while ( p != 0 ){
      tp = _nodePrev[p] ;
      if ( tp < 0 ){
    tp = -tp ;
    _currVol[p][tp] -= v ;
      }
      else
    _currVol[tp][p] += v ;
      p = tp ;
#ifdef debug
      cout << "In fulkerson..." << endl ;
      cout << "v = " << v << endl ;
      cout << "tp = " << tp << endl ;
      for ( int i = 0 ; i <= _nodeNum+1 ; ++i )
    cout << _nodePrev[i] << " " ;
      cout << endl ;
      for ( int i = 1 ; i <= _nodeNum ; ++i ){
    for ( int j = 1 ; j <= _nodeNum ; ++j )
      cout << _currVol[i][j] << " " ;
    cout << endl ;
      }
      cout << "-----------" << endl ;
#endif
    }
  }
  void adjust(){
    for ( int i = 0 ; i < _xNum ; ++i )
      _g[0][_xNode[i]] = true ;
    int newNode = _nodeNum+1 ;
    for ( int i = 1 ; i < _yNum ; ++i )
      _g[_yNode[i]][newNode] = true ;
  }

public:
  BinGraph() {
  }
  void readGraph(){
    cout << "Enter the number of nodes: " ;
    cin >> _nodeNum ;
    cout << "Enter the info of the graph:" << endl ;
    // Adjacent matrix, first get the point in X(p1) and Y(p2), then the edge info from
    // p1 to p2 ;
    int px, py ;
    int edgeNum ;
    cout << "Enter the number of edge: " ;
    cin >> edgeNum ;
    for ( int i = 0 ; i < _nodeNum ; ++i )
      for ( int j = 0 ; j < _nodeNum ; ++j )
    _g[i][j] = false ;
    cout << "Enter the graph info, bool value!" << endl ;
    _xNum = _yNum = 0 ;
    for ( int i = 0 ; i < edgeNum ; ++i ){
      cin >> px >> py ;
      _xNode[_xNum++] = px ;
      _yNode[_yNum++] = py ;
      cin >> _g[px][py] ;
      _g[py][px] = _g[px][py] ;
    }
    return ;
  }
  void process(){
    adjust() ;
    int currNodeNum = _nodeNum + 1 ;
    for ( int i = 0 ; i <= currNodeNum ; ++i )
      for ( int j = 0 ; j <= currNodeNum ; ++j )
    _currVol[i][j] = 0 ;
    int vol ;
    while ( ford(vol) ){
#ifdef debug
      cout << "Ford....." << endl ;
      cout << vol << endl ;
      cout << "............" << endl ;
#endif
      fulkerson(vol) ;
#ifdef debug
      for ( int i = 1 ; i <= _nodeNum ; ++i ){
    for ( int j = 1 ; j <= _nodeNum ; ++j )
      cout << _currVol[i][j] << " " ;
    cout << endl ;
      }
#endif
    }
   
    return ;
  }
  void output() {
    cout << "Maximum binary match is: " << endl ;
    for ( int i = 1 ; i <= _nodeNum ; ++i ){
      for ( int j = 1 ; j <= _nodeNum ; ++j ){
#ifdef debug
    cout << _currVol[i][j] << " " ;
#endif
    if ( _currVol[i][j] == 1 )
      cout << i << "->" << j << endl ;
      }
#ifdef debug
      cout << endl ;
#endif
    }
    cout << endl ;
    return ;
  }
  void printGraph(){
    for ( int i = 0 ; i <= _nodeNum+1 ; ++i ){
      for ( int j = 0 ; j <= _nodeNum+1 ; ++j )
    if ( _g[i][j] )
      cout << 1 << " " ;
    else
      cout << 0 << " " ;
      cout << endl ;
    }
    return ;
  }

} ;


int main( void ){
  BinGraph g ;
  g.readGraph() ;
  g.process() ;
  g.printGraph() ;
  g.output() ;
  system( "pause" ) ;
  return 0 ;
}