SRM 527 450pt : P8XMatrixRecovery
問題概要
0or1の行列(サイズ30*30以下)が与えられて、いくつかのマスには?が入っている。また、各列を適当に置換したものが与えられる。これにも?が入っている場合がある。?を適当に埋めて辞書順最小のものを求める問題。
解法
辞書順最小の定石どおり先頭から順に試す。大丈夫かどうかの判定は二部マッチングをすればよい。
acceptされたコード
計算量O(W^5)くらい。
#include <vector> #include <string> #include <cstring> using namespace std; const int MAX_W = 30; namespace BM{ const int MAX_V = 2 * MAX_W * MAX_W; int V; vector<int> graph[MAX_V]; int match[MAX_V]; bool used[MAX_V]; void clear(){ for(int i=0; i<MAX_V; i++){ graph[i].clear(); } } void add_edge(int u, int v){ graph[v].push_back(u); graph[u].push_back(v); } bool dfs(int v){ used[v] = true; for(int i=0; i<(int)graph[v].size(); i++){ int u = graph[v][i], w = match[u]; if(w<0 || (!used[w] && dfs(w)) ){ match[v] = u; match[u] = v; return true; } } return false; } int bipartite_matching(){ int ret = 0; memset(match, -1, sizeof(match)); for(int v=0; v<V; v++){ if(match[v] < 0){ memset(used, 0, sizeof(used)); if(dfs(v)){ ret++; } } } return ret; } void set_V(int V_){ V = V_; } } using BM::set_V; using BM::add_edge; using BM::bipartite_matching; struct P8XMatrixRecovery { vector <string> solve(vector <string> rows, vector <string> columns) { const int H = rows.size(), W = columns.size(); vector<string> ret = rows; for(int i=0; i<H; i++){ for(int j=0; j<W; j++)if(ret[i][j] == '?'){ ret[i][j] = '0'; if(!check(ret, columns)){ ret[i][j] = '1'; } } } return ret; } bool check(const vector<string>& rows, const vector<string>& columns){ const int H = rows.size(), W = columns.size(); BM::clear(); set_V(2*W); for(int i=0; i<W; i++){ for(int j=0; j<W; j++){ bool ok = true; for(int k=0; k<H; k++){ ok &= (rows[k][i] == '?' || columns[j][k] == '?' || rows[k][i] == columns[j][k]); } if(ok){ add_edge(i, j + W); } } } return bipartite_matching() == W; } };