Codeforces Round #304 Div2 E: Soldier and Traveling（最大フロー問題）

問題

codeforces.com

解法

最大フローやるだけ。

コード

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

public class Main {
	private final int MAX = 10000;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int source = 2 * N;
		int sink = 2 * N + 1;
		MaximumFlow flow = new MaximumFlow(2 * N + 2, source, sink);

		int sumA = 0;
		for (int i = 0; i < N; i++) {
			int a = sc.nextInt();
			flow.addEdge(source, i, a);
			sumA += a;
		}

		int sumB = 0;
		for (int i = 0; i < N; i++) {
			int b = sc.nextInt();
			flow.addEdge(N + i, sink, b);
			sumB += b;
		}
		if (sumA != sumB) {
			System.out.println("NO");
			return;
		}

		for (int i = 0; i < M; i++) {
			int p = sc.nextInt() - 1;
			int q = sc.nextInt() - 1;
			flow.addEdge(p, N + q, MAX);
			flow.addEdge(q, N + p, MAX);
		}
		sc.close();

		for (int i = 0; i < N; i++) {
			// 留まるのもあり
			flow.addEdge(i, N + i, MAX);
		}

		int maximum = flow.fordFulkerson();
		if (maximum == sumB) {
			System.out.println("YES");
			int[][] ans = new int[N][N];
			for (int from = 0; from < N; from++) {
				for (Edge edge : flow.graph[from]) {
					if (edge.to - N >= N) {
						continue;
					}
					ans[from][edge.to - N] = flow.graph[edge.to].get(edge.rev).cap;
				}
			}

			// 出力
			for (int i = 0; i < ans.length; i++) {
				for (int j = 0; j < ans[i].length; j++) {
					System.out.print(ans[i][j]);
					if (j + 1 < ans[i].length) {
						System.out.print(" ");
					}
				}
				System.out.println();
			}
		} else {
			System.out.println("NO");
		}
	}

	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;
	}
}