TopCoder SRM 594 Div1 Medium FoxAndGo3
問題
nxnのグリッドに白石'o'と黒石'x'が置かれている。
何も置かれていない場所は'.'
辺を共有する白石はひとかたまりとみなす。
ひとかたまりの白石が、何も置かれていない場所に隣接していない状態になると、
その白石は全て'.'に変わる。
黒石を好きなだけ置くことができるとき、
グリッドの空いているマスの個数は最大いくつにできるか求めよ。
置かれている黒石や、置いた黒石はなくなることはない。
制約条件
n≦50
初期状態で、白石のかたまりは必ずどこかの'.'と隣接している。
方針
最小カット。
フローグラフを以下のように構成する。
'o'に対応する頂点:その頂点がs-tカットのs側に含まれるとき「そのマスの'o'を取り除く操作をする」という意味の頂点
'.'に対応する頂点:その頂点がs-tカットのs側に含まれるとき「そのマスに'x'を置く操作をする」という意味の頂点
最小カットにしたいので、「損を最小化する」と考える。
すなわち、最大値の上界から、必要最小の損を引いて、利益の最大値を出す。
'o'を取り除く操作に関して、まずは答えに1を足しておく。
操作をしないと、コスト1損するので、
s側に含まれないとき(sとの辺を切ったとき)に1損するようにする。
すなわち、sからその頂点に流量1の辺を張る。
'.'に石を置く操作に関しても、まず答えに1を足す。
操作をするときにコスト1損するので、
s側に含まれるとき(tとの辺を切ったとき)1を損するようにする。
すなわち、その頂点からtへ流量1の辺を張る。
そして、ひとつの'o'の操作を行うためには、その周囲の'.'を全部埋めなければならない。
つまり、'o'の操作に対して絶対に一緒に行わなければならない'.'が存在する。
ここがカットされないように、'o'から'.'へ流量無限大の辺を張る。
(すると最小カットではカットされなくなる)
このようにして作ったグラフでs-t最大フローを求めれば、
最小カットに等しいので、最初に増やしておいた答えから損を引けば答えが求まる。
ソースコード
struct FoxAndGo3{ int h, w; bool v[50][50]; vector<string> board; void dfs(int y, int x, vi &res){ rep(d, 4){ const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1}; int ny = y + dy[d], nx = x + dx[d]; if(ny < 0 || nx < 0 || ny >= h || nx >= w || v[ny][nx]) continue; v[ny][nx] = 1; if(board[ny][nx] == 'o') dfs(ny, nx, res); if(board[ny][nx] == '.') res.pb(ny * w + nx); } } int maxEmptyCells(vector <string> board){ h = board.size(), w = board[0].size(); this->board = board; int ans = 0; int s = h * w, t = s + 1; flowGraph g(h * w + 2); rep(i, h) rep(j, w){ if(board[i][j] == 'o'){ ans++; g.add(s, i * w + j, 1); memset(v, 0, sizeof(v)); vi v; dfs(i, j, v); rep(k, v.size()) g.add(i * w + j, v[k], inf); } if(board[i][j] == '.'){ ans++; g.add(i * w + j, t, 1); } } return ans - g.max_flow(s, t); } };