結果

問題 No.119 旅行のツアーの問題
ユーザー schwarzahlschwarzahl
提出日時 2017-12-22 22:38:41
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,388 bytes
コンパイル時間 3,531 ms
コンパイル使用メモリ 81,620 KB
実行使用メモリ 73,632 KB
最終ジャッジ日時 2023-08-23 09:24:06
合計ジャッジ時間 9,942 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 308 ms
64,468 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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