TopCoder SRM 527 Div1 Medium P8XMatrixRecovery

これは割とすんなり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11176

問題

01で構成された行列rowsが与えられる。
ただし一部要素は0か1かわからない。

ヒント情報として、各列1列分の内容が与えられる。
ただしこちらはどの内容がどの列に対応するかはわからない。
また、ヒント情報も0か1かわからない要素を含む。

行列rowsのうち、ヒント情報と矛盾しない範囲で辞書順最小のものを答えよ。

解法

辞書順最小を答える問題なので、rows中手前の未確定要素から0か1か決めていく。

rowsとヒント情報の矛盾の有無は、rowsの各行とヒント情報の不整合有る無しから二部マッチング問題として書き直すことができる。
よって、未確定要素に0を埋めて完全マッチング可能なら0を埋め、そうでないなら1を埋めていけばよい。

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,E[y].size()});
		E[y].push_back((edge){x,0, E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0 && (tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
				e.capacity -= tf;
				E[e.to][e.reve].capacity += tf;
				return tf;
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};

class P8XMatrixRecovery {
	public:
	
	vector <string> solve(vector <string> rows, vector <string> columns) {
		int R=rows.size(),C=columns.size();
		int i,x,y,z,x1,y1;
		MaxFlow mf;
		
		FOR(y1,R) FOR(x1,C) if(rows[y1][x1]=='?') {
			rows[y1][x1]='0';
			
			MaxFlow mf;
			FOR(i,C) mf.add_edge(0,100+i,1);
			FOR(i,C) mf.add_edge(200+i,300,1);
			FOR(x,C) {
				FOR(y,C) {
					i=1;
					FOR(z,R) if(rows[z][y]!='?' && columns[x][z]!='?' && rows[z][y]!=columns[x][z]) i=0;
					if(i) mf.add_edge(100+x,200+y,1);
				}
			}
			
			if(mf.maxflow(0,300)!=C) rows[y1][x1]='1';
		}
		
		return rows;
	}
};

まとめ

マッチング問題にすることを割と簡単に思いつけたのでよかった。