# CFR 316 C. Tidying Up ( MCMF )

Problem - 316C2 - Codeforces

2 ≤ N * M ≤ 80

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;
}
```