CFR 78 E. Evacuation ( Flow )

Problem - 78E - Codeforces

2 ≤ N ≤ 10
1 ≤ T ≤ 60

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

template< class T >
struct Dinic {
static const int MAXV = 10000;
static constexpr T INF = 1e9;
struct Edge {
int v;
T f;
int re;
Edge( int _v, T _f, int _re ): v( _v ), f( _f ), re( _re ) {}
};
int n, s, t, level[ MAXV ];
vector< Edge > E[ MAXV ];
int now[ MAXV ];
Dinic( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ) {}
void add_edge( int u, int v, T f ) {
E[ u ].emplace_back( v, f, E[ v ].size() );
E[ v ].emplace_back( u, 0, E[ u ].size() - 1 );
}
bool BFS() {
memset( level, -1, sizeof( level ) );
queue< int > que;
que.emplace( s );
level[ s ] = 0;
while( not que.empty() ) {
int u = que.front();
que.pop();
for( auto it: E[ u ] ) {
if( it.f > 0 and level[ it.v ] == -1 ) {
level[ it.v ] = level[ u ] + 1;
que.emplace( it.v );
}
}
}
return level[ t ] != -1;
}
T DFS( int u, T nf ) {
if( u == t ) return nf;
T res = 0;
while( now[ u ] < E[ u ].size() ) {
Edge &it = E[ u ][ now[ u ] ];
if( it.f > 0 and level[ it.v ] == level[ u ] + 1 ) {
T tf = DFS( it.v, min( nf, it.f ) );
res += tf; nf -= tf; it.f -= tf;
E[ it.v ][ it.re ].f += tf;
if( nf == 0 ) return res;
} else ++now[ u ];
}
if( not res ) level[ u ] = -1;
return res;
}
T flow( T res = 0 ) {
while( BFS() ) {
T temp;
memset( now, 0, sizeof( now ) );
while( temp = DFS( s, INF ) ) {
res += temp;
res = min( res, INF );
}
}
return res;
}
};

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

const int MAXN = 10;
const int MAXT = 60;

int N, T;
string G1[ MAXN ];
string G2[ MAXN ];

int fire[ MAXN ][ MAXN ];
int dp[ MAXN ][ MAXN ][ MAXN ][ MAXN ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> T;
for( int i = 0; i < N; ++i ) {
cin >> G1[ i ];
}
for( int i = 0; i < N; ++i ) {
cin >> G2[ i ];
}
{
memset( fire, 0x3f, sizeof( fire ) );
queue< int > que;
for( int i = 0; i < N; ++i ) {
for( int j = 0; j < N; ++j ) {
if( G1[ i ][ j ] == 'Z' ) {
fire[ i ][ j ] = 0;
que.emplace( i * N + j );
}
}
}
while( not que.empty() ) {
int u = que.front();
que.pop();
int x = u / N, y = u % N;
for( int di = 0; di < 4; ++di ) {
int nx = x + dx[ di ];
int ny = y + dy[ di ];
if( not ( 0 <= nx and nx < N and 0 <= nx and ny < N ) ) continue;
if( G1[ nx ][ ny ] == 'Y' ) continue;
if( fire[ nx ][ ny ] > fire[ x ][ y ] + 1 ) {
fire[ nx ][ ny ] = fire[ x ][ y ] + 1;
que.emplace( nx * N + ny );
}
}
}
}
{
memset( dp, 0x3f, sizeof( dp ) );
queue< tuple< int, int, int, int > > que;
for( int i = 0; i < N; ++i ) {
for( int j = 0; j < N; ++j ) {
dp[ i ][ j ][ i ][ j ] = 0;
que.emplace( i, j, i, j );
}
}
while( not que.empty() ) {
int x, y, nx, ny;
tie( x, y, nx, ny ) = que.front();
que.pop();
if( fire[ nx ][ ny ] == dp[ x ][ y ][ nx ][ ny ] ) continue;
for( int di = 0; di < 4; ++di ) {
int nnx = nx + dx[ di ];
int nny = ny + dy[ di ];
if( not ( 0 <= nnx and nnx < N and 0 <= nny and nny < N ) ) continue;
if( G1[ nnx ][ nny ] == 'Y' ) continue;
if( min( fire[ nnx ][ nny ], T ) <= dp[ x ][ y ][ nx ][ ny ] ) continue;
if( dp[ x ][ y ][ nnx ][ nny ] > dp[ x ][ y ][ nx ][ ny ] + 1 ) {
dp[ x ][ y ][ nnx ][ nny ] = dp[ x ][ y ][ nx ][ ny ] + 1;
que.emplace( x, y, nnx, nny );
}
}
}
}
Dinic< int > din( N * N * 2 + 2, N * N * 2, N * N * 2 + 1 );
for( int i = 0; i < N; ++i ) {
for( int j = 0; j < N; ++j ) if( '1' <= G1[ i ][ j ] and G1[ i ][ j ] <= '9' ) {
din.add_edge( N * N * 2, i * N + j, G1[ i ][ j ] - '0' );
for( int k = 0; k < N; ++k ) {
for( int l = 0; l < N; ++l ) if( '1' <= G2[ k ][ l ] and G2[ k ][ l ] <= '9' ) {
if( dp[ i ][ j ][ k ][ l ] == 0x3f3f3f3f ) continue;
din.add_edge( i * N + j, N * N + k * N + l, din.INF );
}
}
}
}
for( int i = 0; i < N; ++i ) {
for( int j = 0; j < N; ++j ) if( '1' <= G2[ i ][ j ] and G2[ i ][ j ] <= '9' ) {
din.add_edge( N * N + i * N + j, N * N * 2 + 1, G2[ i ][ j ] - '0' );
}
}
cout << din.flow() << endl;
return 0;
}
```