結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー schwarzahl
提出日時 2017-12-22 22:38:41
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,388 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,752 ms
コンパイル使用メモリ 83,628 KB
実行使用メモリ 129,032 KB
最終ジャッジ日時 2024-12-21 11:01:44
合計ジャッジ時間 43,644 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

	private void solveA() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] B = new int[N];
		int[] C = new int[N];
		for (int i = 0; i < N; i++) {
			B[i] = sc.nextInt();
			C[i] = sc.nextInt();
		}
		int M = sc.nextInt();
		int[] D = new int[M];
		int[] E = new int[M];
		for (int i = 0; i < M; i++) {
			D[i] = sc.nextInt();
			E[i] = sc.nextInt();
		}
		int ans = 0;

		// 0=s 2*N+1=t
		Integer[][] costGraph = new Integer[2*N+2][];
		for (int i = 0; i < 2*N+2; i++) {
			costGraph[i] = new Integer[2*N+2];
		}
		for (int i = 0; i < N; i++) {
			costGraph[0][i+1] = B[i];
			costGraph[i+1][N+i+1] = B[i] + C[i];
			costGraph[N+i+1][2*N+1] = C[i];
			ans += B[i] + C[i];
		}
		for (int i = 0; i < M; i++) {
			costGraph[N+1+D[i]][1+E[i]] = Integer.MAX_VALUE / 3;
		}
		for (int r = 0; r < 2 * N + 2; r++) {
			for (int c = 0; c < 2 * N + 2; c++) {
				System.err.print(costGraph[r][c] == null ? "Nil " : String.format("%3d", costGraph[r][c] > 999 ? 999 : costGraph[r][c]) + " ");
			}
			System.err.println();
		}
		int current;
		do {
			current = flow(costGraph, 0, new HashSet<>(), Integer.MAX_VALUE / 3, 2 * N + 2);
			ans -= current;
		} while (current > 0);
		for (int r = 0; r < 2 * N + 2; r++) {
			for (int c = 0; c < 2 * N + 2; c++) {
				System.err.print(costGraph[r][c] == null ? "Nil " : String.format("%3d", costGraph[r][c] > 999 ? 999 : costGraph[r][c]) + " ");
			}
			System.err.println();
		}

		System.out.println(ans);
	}

	private int flow(Integer[][] graph, int current_id, Set<Integer> pre_ids, int current_flow, int max_id) {
		pre_ids.add(current_id);
		if (current_id == max_id - 1) {
			return current_flow;
		}
		for (int id = 0; id < max_id; id++) {
			if (graph[current_id][id] != null && graph[current_id][id] > 0 && !pre_ids.contains(id)) {
				int nextFlow = current_flow < graph[current_id][id] ? current_flow : graph[current_id][id];
				int maxFlow = flow(graph, id, new HashSet<>(pre_ids), nextFlow, max_id);
				if (maxFlow > 0) {
					graph[current_id][id] -= maxFlow;
					if (graph[id][current_id] == null) {
						graph[id][current_id] = 0;
					}
					graph[id][current_id] += maxFlow;
					return maxFlow;
				}
			}
		}
		return 0;
	}
}
0