TopCoder SRM 539 Div1 Medium: SafeReturn

解法

kmjp.hatenablog.jp

やることは、 ワーシャルフロイト + 二部グラフの最大マッチング（最大フロー）

ワーシャルフロイトで2点間の距離を出しておくと、最短距離を通る時にその頂点を通過するか確認することが出来る。

for (int x = 0; x < N; x++) {
	for (int y = 0; y < N; y++) {
		if (map[0][x + 1] + map[x + 1][y + 1] == map[0][y + 1]) {
			//0からy+1に行く兵士がx+1を経由する時
		}
	}
}

例えば、兵士3が0->1->2->3の経路を辿って行く時、兵士1は兵士2に護衛され、兵士1と兵士2は兵士3に護衛されている。
この時、

1->2
1->3
2->3

という有効辺をもつグラフの最大マッチングっぽい感じが出てくる。

同じ兵士について、「護衛する側」と「護衛される側」で分けて考えると2部グラフの最大マッチング問題へ帰着できるので、最大フローで解くことができる。

コード

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

public class SafeReturn {
	private final int INF = 1 << 10;

	public int minRisk(int N, String[] streets) {
		int T = streets.length;
		int[][] map = new int[T][T];
		for (int i = 0; i < T; i++) {
			for (int j = 0; j < T; j++) {
				if (streets[i].charAt(j) == '-') {
					map[i][j] = INF;
				} else {
					map[i][j] = streets[i].charAt(j) - '0';
				}
			}
		}

		for (int k = 0; k < T; k++) {
			for (int i = 0; i < T; i++) {
				for (int j = 0; j < T; j++) {
					map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
				}
			}
		}

		// 「護衛される側」と「護衛する側」で二部マッチングする。
		// 護衛される側: 0-(N-1)
		// 護衛する側: N-(2*N-1)
		int V = 2 * N + 2;
		int source = 2 * N;
		int sink = 2 * N + 1;
		MaximumFlow flow = new MaximumFlow(V, source, sink);
		for (int x = 0; x < N; x++) {
			flow.addEdge(source, x, 1);
		}
		for (int x = 0; x < N; x++) {
			flow.addEdge(N + x, sink, 1);
		}
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				if (map[0][x + 1] + map[x + 1][y + 1] == map[0][y + 1]) {
					// y+1に行く兵士がx+1に行く兵士を護衛すれば良い
					flow.addEdge(x, N + y, 1);
				}
			}
		}

		return N - flow.fordFulkerson();
	}

}

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