SRM575 Div1 Hard "TheTilesDivOne"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12500
訳
Div2 Hardと同じ
制約
1 <= チェスボードの高さ <= 47
1 <= チェスボードの幅 <= 47
解法
コチラを参考にしました。m(_ _)m
TopCoder SRM 575 Div1 Hard TheTilesDivOne - kmjp's blog
蟻本のP179のコラムもヒントになります。
白マスを奇数偶数にわけるという発想がでなかった!残念!
黒マスを示す頂点に一度しか流さないようにするために、
黒マス(使用前)→黒マス(使用後)とする必要があったのか。
いやこれいらないよな?と思って黒マス頂点1つで実装したら、
見事にSample0でWAになりました。
ソースコード
class MaxFlow{ public: MaxFlow( int max_n ); ~MaxFlow(); int get( int s, int t ); void addEdge( int from, int to, int cap ); void printGraph(); private: int dfs( int v, int t, int cap ); struct Edge{ int to, cap, rev; }; int max_n; vector<Edge>* G; bool* use; }; class TheTilesDivOne { public: int find(vector <string> board){ int H = board.size(); int W = board[0].length(); int offset = H * W; int S = 2 * H * W; int T = 2 * H * W + 1; MaxFlow mf( 2 * H * W + 2 ); // S -> 奇数の白マス for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( x % 2 == 0 || (x + y) % 2 == 0 ) continue; if( board[y][x] == 'X' ) continue; int id = y * W + x; mf.addEdge( S, id, 1 ); } } int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; // 奇数の白マス -> 黒マス for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( x % 2 == 0 || (x + y) % 2 == 0 ) continue; if( board[y][x] == 'X' ) continue; int wid = y * W + x; for( int d = 0; d < 4; d++ ){ int bx = x + dx[d], by = y + dy[d]; if( 0 <= bx && bx < W && 0 <= by && by < H && board[by][bx] == '.' ){ int bid = by * W + bx; mf.addEdge( wid, bid, 1 ); } } } } // 黒マス(使用前) -> 黒マス(使用後) for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( (x + y) % 2 ) continue; if( board[y][x] == 'X' ) continue; int bid = y * W + x; mf.addEdge( bid, bid + offset, 1 ); } } // 黒マス(使用後) -> 偶数の白マス for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( (x + y) % 2 ) continue; if( board[y][x] == 'X' ) continue; int bid = y * W + x + offset; for( int d = 0; d < 4; d++ ){ int wx = x + dx[d], wy = y + dy[d]; if( 0 <= wx && wx < W && 0 <= wy && wy < H && board[wy][wx] == '.' && wx % 2 == 0 ){ int wid = wy * W + wx; mf.addEdge( bid, wid, 1 ); } } } } // 偶数の白マス -> T for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( x % 2 || (x + y) % 2 == 0 ) continue; if( board[y][x] == 'X' ) continue; int id = y * W + x; mf.addEdge( id, T, 1 ); } } return mf.get( S, T ); } }; // 以下 class MaxFlowの定義 MaxFlow::MaxFlow( int _max_n ){ max_n = _max_n; G = new vector<Edge>[max_n]; use = new bool[max_n]; } MaxFlow::~MaxFlow(){ delete[] G; G = 0; delete[] use; use = 0; } void MaxFlow::addEdge( int from, int to, int cap ){ Edge e1 = { to, cap, G[to].size() }; G[from].push_back(e1); Edge e2 = { from, 0, G[from].size()-1 }; G[to].push_back(e2); } int MaxFlow::dfs( int v, int t, int cap ){ if( v == t ) return cap; use[v] = true; int n = G[v].size(); for( int i = 0; i < n; i++ ){ Edge& e = G[v][i]; if( e.cap == 0 || use[e.to] ) continue; int flow = dfs( e.to, t, min(cap, e.cap) ); if( 0 < flow ){ e.cap -= flow; G[e.to][e.rev].cap += flow; return flow; } } return 0; } int MaxFlow::get( int s, int t ){ int res = 0; while( true ){ memset( use, false, sizeof(bool)*max_n ); int add = dfs( s, t, INT_MAX ); if( add == 0 ) break; res += add; } return res; } void MaxFlow::printGraph(){ for( int i = 0; i < max_n; i++ ){ printf( "%d - ", i ); int n = G[i].size(); for( int j = 0; j < n; j++ ){ printf( "\tto=%d cp=%d rev=%d\n", G[i][j].to, G[i][j].cap, G[i][j].rev ); } printf( "\n" ); } }