SRM527 Div1 Medium - P8XMatrixRecovery

TopCoder SRM
問題

h行w列で各要素が '0' か '1' か '?' のみからなる行列が2つ与えられる(それぞれhs, wsとする)
これらの行列の '?' を0か1に書き換えて同じ行列にするとき、辞書順最小のものを求めよ

1 <= h, w <= 30
2つの行列を一致させる方法が少なくとも1つは存在することが保証される

解法

辞書順最小の条件より、0にしても問題が起こらない '?' は全部0にするべき
手前の要素から順に見ていき、'?' を見つける度にとりあえず0にしてみて、それで問題が起こらなければそのまま次に進めば良いし、問題が起きるなら1にするしかない
これを繰り返せば良さそう
あとは問題が起きるかどうかを判定する方法さえわかれば解ける

hsの列を一個ずつ見ていき、wsの列のうち両者の '?' をうまく変えれば一致させることができるような列と辺で結ぶ
すると二部グラフができる
条件を満たすような '?' の埋め方が存在するということは、この二部グラフに完全マッチングが存在することと同値である
二部グラフの最大マッチングはFordFulkerson法とかDinic法で求められる
→ 解けた🤠

計算量はO(hw^3(h+w))くらいかな

実装

dinicは蟻本p194の丸パクリ
二部グラフの頂点番号は、始点を0、hsの各列を1〜w、wsの各列をw+1〜2w、終点を100とした
始点からhsの各列へ容量1の辺を貼り、hsの各列からwsの(一致させられる)各列へ容量1の辺を貼り、wsの各列から終点へ容量1の辺を貼る

最初TLEしてどこで無駄なことしてんのかなって結構悩んだんだけど、デバッグ用の出力でめっちゃ時間かかってるだけだった
今後気を付ける

const int MAXV = 123;
class Dinic {
private:
struct edge {int to, cap, rev;};
	vector<edge> g[MAXV];
	int level[MAXV], iter[MAXV];
public:
	// fromからtoへ向かう要領capの辺をグラフに追加する
	void add_edge(int from, int to, int cap) {
		g[from].push_back((edge){to, cap, (int)g[to].size()});
		g[to].push_back((edge){from, 0, (int)g[from].size()-1});
	}
	// sからの最短距離をBFSで計算
	void bfs(int s) {
		memset(level, -1, sizeof(level));
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (int i = 0; i < g[v].size(); i++) {
				edge &e = g[v][i];
				if (e.cap>0 && level[e.to]<0) {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}
	// 増加パスをdfsで探す
	int dfs(int v, int t, int f) {
		if (v==t) return f;
	for (int &i = iter[v]; i < g[v].size(); ++i) {
			edge &e = g[v][i];
			if (e.cap>0 && level[v]<level[e.to]) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d>0) {
					e.cap -= d;
					g[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	// sからtへの最大流を求める
	int getflow(int s, int t) {
		int flow = 0;
		while (1) {
			bfs(s);
			if (level[t]<0) return flow;
			memset(iter, 0, sizeof(iter));
			int f;
			while ((f=dfs(s, t, inf))>0) flow += f;
		}
	}
};

class P8XMatrixRecovery {
public:
	int h, w;
	vector<string> rs, cs;

	bool ok() {
		Dinic din;
		rep(i,w) rep(j,w) {
			bool ng = 0;
			rep(k,h) if (rs[k][i]!='?' && cs[j][k]!='?' && rs[k][i]!=cs[j][k]) {
				ng = 1;
				break;
			}
			if (!ng) din.add_edge(i+1,w+j+1,1);
		}
		rep(i,w) din.add_edge(0,i+1,1), din.add_edge(w+i+1,100,1);
		return din.getflow(0,100)==w;
	}

	vector<string> solve(vector<string> R, vector<string> C) {
		rs = R, cs = C, h = rs.size(), w = cs.size();
		rep(i,h) rep(j,w) if (rs[i][j]=='?') {
			rs[i][j] = '0';
			if (!ok()) rs[i][j] = '1';
		}
		return rs;
	}
};