読者です 読者をやめる 読者になる 読者になる

天下一プログラマーコンテスト2015予選A C: 天下一美術館

問題

tenka1-2015-quala.contest.atcoder.jp

解法

http://tenka1.klab.jp/2015/explain/quala_c.htmltenka1.klab.jp

隣り合った2マスが両方Bと違い、かつ、入れ替えればBと一致する場合、それらを1つずつ変えるより入れ替えた方が少ないコストで済む。
これは「二部グラフの最大マッチング問題」に帰結することができ、これは最大フロー問題として解くことができる。

http://dopal.cs.uec.ac.jp/okamotoy/lect/2012/graphtheory/lect12.pdf

コード

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

public class Main {
	private final int[] DX = { 0, 0, 1, -1 };
	private final int[] DY = { 1, -1, 0, 0 };

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int M = scanner.nextInt();
		int N = scanner.nextInt();

		int[][] A = new int[M][N];
		int[][] B = new int[M][N];
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				A[i][j] = scanner.nextInt();
			}
		}
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				B[i][j] = scanner.nextInt();
			}
		}
		scanner.close();

		// AとBで違う色のマスの数をカウントしておく
		int cnt = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (A[i][j] != B[i][j]) {
					cnt++;
				}
			}
		}

		// 各マスを1つの頂点として、スタートとゴールを入れたM*N+2頂点のグラフを作る
		int V = M * N;
		int source = V;
		int sink = V + 1;
		MaximumFlow graph = new MaximumFlow(V + 2, source, sink);

		for (int m = 0; m < M; m++) {
			for (int n = 0; n < N; n++) {
				if (A[m][n] == B[m][n]) {
					continue;
				}

				// 入ってくるマスと出ていくマスが市松模様になるように設定する
				int from = m * N + n;
				if (m % 2 != n % 2) {
					graph.addEdge(from, sink, 1);
					continue;
				}
				graph.addEdge(source, from, 1);

				// Aの中の隣り合っているマスが両方ともBと違い、かつ、入れ替えた時に両方ともBに一致する時
				for (int d = 0; d < 4; d++) {
					int mm = m + DX[d];
					int nn = n + DY[d];
					if (mm < 0 || nn < 0 || mm >= M || nn >= N) {
						continue;
					}
					int to = mm * N + nn;
					if (A[mm][nn] != B[mm][nn] && A[m][n] != A[mm][nn]) {
						graph.addEdge(from, to, 1);
					}
				}
			}
		}

		// 最大マッチング
		int match = graph.fordFulkerson();

		// match*2個のマスがコストmatchによってBに一致したので、1つづ使えるよりmatchだけ減る
		System.out.println(cnt - match);
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}

// 最大フロー問題のライブラリ
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;
	}
}