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