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

};