CFR 513 F. Scaygerboss ( Flow, Binary Search )

Problem - 513F2 - Codeforces

題意：
有個 N * M 棋盤，有些格子是障礙。
有一個怪盜，以及 Males 個男生，Females 個女生。
這些人都會用 r, c, t 表示座標位置以及移動一單位距離所需要的時間。
問至少要多少時間，才能使每個人都恰好和一位異性在同一個格子上。
怪盜可以選擇要成為男性或者女性。

制約：
1 ≤ N, M ≤ 22

解法：
對所有人求出對所有格子的最短路徑。
二分搜答案，每次重新建圖。
模型很顯然，詳見代碼。

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

template< class T >
struct Dinic {
  static const int MAXV = 20000;
  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 MAXN = 22;
const int MAXM = 22;

int N, M, Males, Females;
string G[ MAXN ];
int R[ MAXN * MAXM * 2 + 1 ], C[ MAXN * MAXM * 2 + 1 ], T[ MAXN * MAXM * 2 + 1 ];

long long dp[ MAXN * MAXM * 2 + 1 ][ MAXN ][ MAXM ];

signed main() {
  ios::sync_with_stdio( false );
  {
    cin >> N >> M >> Males >> Females;
    for( int i = 0; i < N; ++i ) {
      cin >> G[ i ];
    }
    if( Males + 1 == Females ) {
      ++Males;
    } else if( Females + 1 == Males ) {
      cin >> R[ Males + Females ] >> C[ Males + Females ] >> T[ Males + Females ];
      --R[ Males + Females ], --C[ Males + Females ];
    } else {
      cout << -1 << endl;
      exit( 0 );
    }
    for( int i = 0; i < Males; ++i ) {
      cin >> R[ i ] >> C[ i ] >> T[ i ];
      --R[ i ], --C[ i ];
    }
    for( int i = 0; i < Females; ++i ) {
      cin >> R[ Males + i ] >> C[ Males + i ] >> T[ Males + i ];
      --R[ Males + i ], --C[ Males + i ];
    }
    if( T[ Males + Females ] ) {
      ++Females;
    }
  }
  {
    memset( dp, 0x3f, sizeof( dp ) );
    priority_queue< tuple< long long, int, int, int > > pq;
    for( int i = 0; i < Males + Females; ++i ) {
      pq.emplace( dp[ i ][ R[ i ] ][ C[ i ] ] = 0LL, i, R[ i ], C[ i ] );
    }
    while( not pq.empty() ) {
      long long dis;
      int who, x, y;
      tie( dis, who, x, y ) = pq.top();
      pq.pop();
      dis *= -1;
      if( dp[ who ][ x ][ y ] != dis ) continue;
      for( int di = 0; di < 4; ++di ) {
        const static int dx[] = { 0, 1, 0, -1 };
        const static int dy[] = { 1, 0, -1, 0 };
        int nx = x + dx[ di ];
        int ny = y + dy[ di ];
        if( not ( 0 <= nx and nx < N and 0 <= ny and ny < M ) ) continue;
        if( G[ nx ][ ny ] == '#' ) continue;
        if( dp[ who ][ nx ][ ny ] > dis + T[ who ] ) {
          pq.emplace( -( dp[ who ][ nx ][ ny ] = dis + T[ who ] ), who, nx, ny );
        }
      }
    }
  }
  {
    long long lb = -1, ub = 1e12;
    while( lb + 1 != ub ) {
      long long mid = lb + ub >> 1;
      int SRC = 2 * N * M + Males + Females, DST = SRC + 1;
      Dinic< int > din( DST + 1, SRC, DST );
      for( int i = 0; i < Males; ++i ) {
        din.add_edge( SRC, 2 * N * M + i, 1 );
        for( int x = 0; x < N; ++x ) {
          for( int y = 0; y < M; ++y ) {
            if( mid < dp[ i ][ x ][ y ] ) continue;
            din.add_edge( 2 * N * M + i, x * M + y, 1 );
          }
        }
      }
      for( int x = 0; x < N; ++x ) {
        for( int y = 0; y < M; ++y ) {
          din.add_edge( x * M + y, N * M + x * M + y, 1 );
        }
      }
      for( int i = 0; i < Females; ++i ) {
        for( int x = 0; x < N; ++x ) {
          for( int y = 0; y < M; ++y ) {
            if( mid < dp[ Males + i ][ x ][ y ] ) continue;
            din.add_edge( N * M + x * M + y, 2 * N * M + Males + i, 1 );
          }
        }
        din.add_edge( 2 * N * M + Males + i, DST, 1 );
      }
      ( din.flow() == Males ? ub : lb ) = mid;
    }
    cout << ( ub == 1e12 ? -1 : ub ) << endl;
  }
  return 0;
}