CFR 316 C. Tidying Up ( MCMF )

Problem - 316C2 - Codeforces

題意：
給一個 N * M 的矩陣，裡面有 N * M 個數字，[ 1, N * M / 2 ] 各出現兩次。
問最少要將幾個格子裡的數字移位，才能使得存在一種匹配，每個匹配都是相鄰的兩格子，且內容相同。

制約：
2 ≤ N * M ≤ 80

解法：
用最大流保證每個格子都有被匹配到，用最小費用來計算答案。
將矩陣黑白塗色 ( 相鄰格子異色 )，黑色格子連到白色格子若且唯若它們相鄰，容量 1，費用 = 0 if same else 1。

複雜度：
O( ( N * M )**2 )

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

template< class TF, class TC >
struct CostFlow {
  static const int MAXV = 10000;
  static constexpr TC INF = 1e9;
  struct Edge {
    int v, r;
    TF f;
    TC c;
    Edge( int _v, int _r, TF _f, TC _c ): v( _v ), r( _r ), f( _f ), c( _c ) {}
  };
  int n, s, t, pre[ MAXV ], pre_E[ MAXV ], inq[ MAXV ];
  TF fl;
  TC dis[ MAXV ], cost;
  vector< Edge > E[ MAXV ];
  CostFlow( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ), fl( 0 ), cost( 0 ) {}
  void add_edge( int u, int v, TF f, TC c ) {
    E[ u ].emplace_back( v, E[ v ].size(), f, c );
    E[ v ].emplace_back( u, E[ u ].size() - 1, 0, -c );
  }
  pair< TF, TC > flow() {
    while( true ) {
      for( int i = 0; i < n; ++i ) {
        dis[ i ] = INF;
        inq[ i ] = 0;
      }
      dis[ s ] = 0;
      queue< int > que;
      que.emplace( s );
      while( not que.empty() ) {
        int u = que.front();
        que.pop();
        inq[ u ] = 0;
        for( int i = 0; i < E[ u ].size(); ++i ) {
          int v = E[ u ][ i ].v;
          TC w = E[ u ][ i ].c;
          if( E[ u ][ i ].f > 0 and dis[ v ] > dis[ u ] + w ) {
            pre[ v ] = u;
            pre_E[ v ] = i;
            dis[ v ] = dis[ u ] + w;
            if( not inq[ v ] ) {
              inq[ v ] = 1;
              que.emplace( v );
            }
          }
        }
      }
      if( dis[ t ] == INF ) break;
      TF tf = INF;
      for( int v = t, u, l; v != s; v = u ) {
        u = pre[ v ];
        l = pre_E[ v ];
        tf = min( tf, E[ u ][ l ].f );
      }
      for( int v = t, u, l; v != s; v = u ) {
        u = pre[ v ];
        l = pre_E[ v ];
        E[ u ][ l ].f -= tf;
        E[ v ][ E[ u ][ l ].r ].f += tf;
      }
      cost += tf * dis[ t ];
      fl += tf;
    }
    return { fl, cost };
  }
};

const int MAXN = 80;
const int MAXM = 80;

int N, M;
int G[ MAXN ][ MAXM ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ) {
    for( int j = 0; j < M; ++j ) {
      cin >> G[ i ][ j ];
    }
  }
  CostFlow< int, int > mcmf( N * M + 2, N * M, N * M + 1 );
  for( int i = 0; i < N; ++i ) {
    for( int j = 0; j < M; ++j ) {
      if( i + j & 1 ) {
        mcmf.add_edge( N * M, i * M + j, 1, 0 );
        static const int dx[] = { 0, 1, 0, -1 };
        static const int dy[] = { 1, 0, -1, 0 };
        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 < M ) ) continue;
          mcmf.add_edge( i * M + j, ni * M + nj, 1, G[ i ][ j ] != G[ ni ][ nj ] );
        }
      } else {
        mcmf.add_edge( i * M + j, N * M + 1, 1, 0 );
      }
    }
  }
  cout << mcmf.flow().second << endl;
  return 0;
}