0w1

ARC 074 F - Lotus Leaves ( Flow, Mincut )

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder

題意:
H * W 的棋盤。
起點 S,終點 T。這兩個點都有葉子。
其他葉子用 'o' 描述。
每次可以選擇同行或同列的 'o' 移動到那裡。
問最少要移除多少葉子才能使 S 不能到達 T。無解輸出 -1。

制約:
2≤H,W≤100
aij は ., o, S, T のどれかである。
aij のうち S はちょうど 1 個存在する。
aij のうち T はちょうど 1 個存在する。

解法:
顯然是最小割=最大流。
重要的不是點,而是行和列。
每次移動事實上的變化是行或列其中之一的變化。
因此把行和列抽象成節點,把葉子抽象成邊。

#include <bits/stdc++.h>
using namespace std;
 
template< class T >
struct Dinic {
  static const int MAXV = 10000;
  static const T INF = 0x3f3f3f3f;
  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, bool bidirectional = false ) {
    E[ u ].emplace_back( v, f, E[ v ].size() );
    E[ v ].emplace_back( u, 0, E[ u ].size() - 1 );
    if( bidirectional ) {
      E[ v ].emplace_back( u, f, 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 MAXH = 100;
const int MAXW = 100;
 
int H, W;
string G[ MAXH ];
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> H >> W;
  for( int i = 0; i < H; ++i ) {
    cin >> G[ i ];
  }
  int SOURCE = H + W;
  int SINK = H + W + 1;
  Dinic< int > din( H + W + 2, SOURCE, SINK );
  for( int i = 0; i < H; ++i ) {
    for( int j = 0; j < W; ++j ) {
      if( G[ i ][ j ] == 'S' ) {
        din.add_edge( SOURCE, i, din.INF );
        din.add_edge( SOURCE, H + j, din.INF );
      } else if( G[ i ][ j ] == 'T' ) {
        din.add_edge( i, SINK, din.INF );
        din.add_edge( H + j, SINK, din.INF );
      } else if( G[ i ][ j ] == 'o' ) {
        din.add_edge( i, H + j, 1 );
        din.add_edge( H + j, i, 1 );
      }
    }
  }
  int ans = din.flow();
  if( ans >= din.INF ) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}