POI 2 Stage 2 Board Covering ( Bipartite Matching )

http://main.edu.pl/en/archive/oi/2/sza

題意：
給一個 N * N 的棋盤，X, Y, Z 三塊為不用覆蓋的，求是否可以用 2 * 1 ( 可旋轉 ) 的東西覆蓋滿棋盤，可以的話輸出方案。

資料規模：
In the only line of the standard input there are written four numbers separated by single spaces. The first number is the dimension of the board n, and the three other are the numbers of the cut out squares. The last number is followed by the end of the line.

解法：
棋盤問題可以考慮黑白圖色，那麼黑色匹配白色，代表這兩個可以被覆蓋。要求的即是二分圖完美匹配方案。用匈牙利算法解決。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

int N, X, Y, Z;
vector< int > G[ MAXN * MAXN ];
int bf[ MAXN * MAXN ];

bool find_mate( int u, vector< int > &vis ){
  for( int i = 0; i < G[ u ].size(); ++i ){
    int v = G[ u ][ i ];
    if( vis[ v ] ) continue;
    vis[ v ] = 1;
    if( bf[ v ] == -1 or find_mate( bf[ v ], vis ) ){
      bf[ v ] = u;
      return true;
    }
  }
  return false;
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> X >> Y >> Z;
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < N; ++j ){
      if( i + j & 1 ) continue;
      int p = i * N + j + 1;
      if( p == X or p == Y or p == Z ) continue;
      for( int di = 0; di < 4; ++di ){
        int ni = i + dx[ di ];
        int nj = j + dy[ di ];
        if( not ( 0 <= ni and ni < N and 0 <= nj and nj < N ) ) continue;
        int np = ni * N + nj + 1;
        if( np == X or np == Y or np == Z ) continue;
        G[ i * N + j ].push_back( ni * N + nj );
      }
    }
  }
  { // bipartite matching
    int mcnt = 0;
    memset( bf, -1, sizeof( bf ) );
    for( int i = 0; i < N; ++i ){
      for( int j = 0; j < N; ++j ){
        if( i + j & 1 ) continue;
        int p = i * N + j + 1;
        if( p == X or p == Y or p == Z ) continue;
        vector< int > vis( N * N );
        if( not find_mate( i * N + j, vis ) ){
          cout << "NIE\n";
          exit( 0 );
        }
        ++mcnt;
      }
    }
    if( mcnt < ( N * N - 3 ) / 2 ){
      cout << "NIE\n";
      exit( 0 );
    }
  }
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < N; ++j ){
      if( ~ ( i + j ) & 1 ) continue;
      if( bf[ i * N + j ] == -1 ) continue;
      cout << i * N + j + 1 << " " << bf[ i * N + j ] + 1 << "\n";
    }
  }
  return 0;
}