TopCoder SRM 527 Div1 Medium: P8XMatrixRecovery

解法

辞書順最小なので，前の方から0を入れ，ダメなら1に変える，というふうに貪欲に決めていく．

ある'?'を0にした時に矛盾がないかどうかは，その都度rowsの各列とcolumnsの各列が矛盾なくマッチングできるかどうかを調べる．
2部マッチングは最大流問題として解くことができる．

kenkoooo.hatenablog.com

コード

import java.util.ArrayList;
import java.util.Arrays;

public class P8XMatrixRecovery {
	private int R, C;

	public String[] solve(String[] rows, String[] columns) {
		R = rows.length;
		C = columns.length;

		// 使いやすいようにcharにする
		char[][] rmap = new char[R][];
		for (int i = 0; i < R; i++) {
			rmap[i] = rows[i].toCharArray();
		}
		char[][] cmap = new char[C][];
		for (int i = 0; i < C; i++) {
			cmap[i] = columns[i].toCharArray();
		}

		// 前にある'?'から順番に0を入れていき，無理だったら1にする
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (rmap[r][c] == '?') {
					// とりあえず0を入れる
					rmap[r][c] = '0';
					if (!check(rmap, cmap)) {
						// 無理なら1に変える
						rmap[r][c] = '1';
					}
				}
			}
		}

		// 出力
		String[] ans = new String[R];
		for (int i = 0; i < R; i++) {
			ans[i] = String.valueOf(rmap[i]);
		}
		return ans;
	}

	private boolean check(char[][] rmap, char[][] cmap) {
		// rmapとcmapの各列を頂点として2部マッチングし，出来るならtrue
		int V = C * 2 + 2;
		int source = V - 2;
		int sink = V - 1;

		MaximumFlow flow = new MaximumFlow(V, source, sink);
		for (int i = 0; i < C; i++) {
			outer: for (int j = 0; j < C; j++) {
				// rmap[][i]とcmap[j]がマッチできるか
				for (int row = 0; row < R; row++) {
					if (rmap[row][i] != '?' && cmap[j][row] != '?'
							&& rmap[row][i] != cmap[j][row]) {
						continue outer;
					}
				}
				flow.addEdge(i, C + j, 1);
			}
		}

		// スタートからrmapの各列に，cmapの各列からゴールに，それぞれ辺を張る
		for (int i = 0; i < C; i++) {
			flow.addEdge(source, i, 1);
			flow.addEdge(C + i, sink, 1);
		}

		return flow.fordFulkerson() == C;
	}

}

// 最大フロー問題のライブラリ
class MaximumFlow {
	public static final int INF = 100000000;

	int V;// 頂点数
	int source;
	int sink;

	ArrayList<Edge>[] graph;
	boolean[] used;

	@SuppressWarnings("unchecked")
	public MaximumFlow(int V, int source, int sink) {
		this.V = V;
		this.source = source;
		this.sink = sink;
		graph = new ArrayList[V];
		for (int i = 0; i < V; i++) {
			graph[i] = new ArrayList<Edge>();
		}
		used = new boolean[V];
	}

	public void addEdge(int from, int to, int cap) {
		graph[from].add(new Edge(to, cap, graph[to].size()));
		graph[to].add(new Edge(from, 0, graph[from].size() - 1));
	}

	public int fordFulkerson() {
		int flow = 0;
		while (true) {
			Arrays.fill(used, false);
			int f = dfsFF(source, sink, INF);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}

	private int dfsFF(int from, int to, int flow) {
		if (from == to) {
			return flow;
		}
		used[from] = true;

		for (Edge edge : graph[from]) {
			if (used[edge.to] || edge.cap <= 0) {
				continue;
			}
			int d = dfsFF(edge.to, to, Math.min(flow, edge.cap));
			if (d > 0) {
				edge.cap -= d;
				graph[edge.to].get(edge.rev).cap += d;
				return d;
			}
		}
		return 0;
	}
}

class Edge {
	int to;
	int cap;
	int rev;

	public Edge(int to, int cap, int rev) {
		this.to = to;
		this.cap = cap;
		this.rev = rev;
	}
}