CFR 78 E. Evacuation ( Flow )

Problem - 78E - Codeforces

題意：
在 N * N 的地圖上，有一些格子是障礙物，有些有若干個科學家，有些有若干個氧氣筒。
在時刻 0，某個障礙物腐朽瓦解，發出毒氣，並向相鄰非障礙物的格子以一單位時間一格的速率擴散。
科學家只要移動到有氧氣筒的地方，就能瞬間得救，但一個氧氣筒只能供應一個科學家。
科學家的移動速率和毒氣的移動速率相同，模式也一樣。
科學家碰到毒氣的瞬間就會死亡，但特別的，如果科學家和毒氣同時到有氧氣筒的格子，並且科學家使用氧氣筒，科學家就會安全。
在時刻 T 結束的瞬間，沒有得到氧氣筒的科學家會瞬間死亡。
問最多可以有多少科學家存活。

制約：
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;
}