結果

問題 No.177 制作進行の宮森あおいです！
ユーザー GrenacheGrenache
提出日時 2016-06-09 21:29:35
言語 Java21
(openjdk 21)
結果
AC  
実行時間 212 ms / 2,000 ms
コード長 3,434 bytes
コンパイル時間 4,406 ms
コンパイル使用メモリ 80,204 KB
実行使用メモリ 44,196 KB
最終ジャッジ日時 2024-04-17 12:46:55
合計ジャッジ時間 7,639 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 146 ms
41,948 KB
testcase_01 AC 149 ms
41,884 KB
testcase_02 AC 143 ms
41,660 KB
testcase_03 AC 167 ms
41,764 KB
testcase_04 AC 159 ms
41,912 KB
testcase_05 AC 188 ms
42,656 KB
testcase_06 AC 205 ms
42,824 KB
testcase_07 AC 181 ms
42,028 KB
testcase_08 AC 184 ms
42,152 KB
testcase_09 AC 210 ms
44,196 KB
testcase_10 AC 212 ms
43,356 KB
testcase_11 AC 211 ms
43,468 KB
testcase_12 AC 209 ms
43,304 KB
testcase_13 AC 134 ms
41,628 KB
testcase_14 AC 132 ms
41,660 KB
testcase_15 AC 133 ms
41,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;


public class Main_yukicoder177 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

		int w = sc.nextInt();
		int n = sc.nextInt();

		int[] j = new int[n];
		for (int i = 0; i < n; i++) {
			j[i] = sc.nextInt();
		}

		int m = sc.nextInt();

		int[] c = new int[m];
		for (int i = 0; i < m; i++) {
			c[i] = sc.nextInt();
		}

		List<Set<Integer>> ng = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			Set<Integer> tmp = new HashSet<>();
			int q = sc.nextInt();
			for (int k = 0; k < q; k++) {
				tmp.add(sc.nextInt() - 1);
			}
			ng.add(tmp);
		}

		Dinic di = new Dinic(n + m + 2);

		for (int i = 0; i < n; i++) {
			di.addEdge(0, i + 2, j[i]);
		}

		for (int i = 0; i < m; i++) {
			di.addEdge(i + n + 2, 1, c[i]);
		}

		for (int i = 0; i < n; i++) {
			for (int k = 0; k < m; k++) {
				if (!ng.get(k).contains(i)) {
					di.addEdge(i + 2, k + n + 2, w);
				}
			}
		}

		if (di.getMaxflow(0, 1) >= w) {
			System.out.println("SHIROBAKO");
		} else {
			System.out.println("BANSAKUTSUKITA");
		}

		sc.close();
	}

	private static class Dinic {
		private static final int INF = Integer.MAX_VALUE;
		ArrayList<Edge>[] edges;
		int n;

		@SuppressWarnings("unchecked")
		Dinic(int n) {
			this.n = n;
			edges = new ArrayList[n];
			for (int ii = 0; ii < n; ii++) {
				edges[ii] = new ArrayList<Edge>();
			}
			checkedTo = new int[this.n];
			level = new int[this.n];
		}

		// i, j:0-indexed
		public void addEdge(int i, int j, int c) {
			edges[i].add(new Edge(j, c, edges[j].size(), false));
			// add reverse edge
			edges[j].add(new Edge(i, c, edges[i].size() - 1, true));
		}

		public int getMaxflow(int s, int t) {
			// initialize flow
			for (int i = 0; i < edges.length; i++) {
				for (Edge e : edges[i]) {
					if (!e.revFlag) {
						e.f = 0;
					} else {
						e.f = e.w;
					}
				}
			}

			int ret = 0;
			while (true) {
				Arrays.fill(level, -1);
				bfs(s);
				if (level[t] == -1) {
					break;
				}

				Arrays.fill(checkedTo, 0);
				int augmentation;
				while ((augmentation = dfs(s, t, INF)) > 0) {
					ret += augmentation;
				}
			}

			return ret;
		}

		private static int[] checkedTo;
		private static int[] level;

		// no capacity edges must be removed
		private void bfs(int s) {
			Queue<Integer> q = new ArrayDeque<Integer>();
			level[s] = 0;
			q.add(s);
			while (!q.isEmpty()) {
				int u = q.remove();
				for (Edge e : edges[u]) {
					if (level[e.v] == -1 && e.w - e.f > 0) {
						level[e.v] = level[u] + 1;
						q.add(e.v);
					}
				}
			}
		}

		// find max flow (less than f), on u -> v path
		// next vertex must has larger level
		private int dfs(int u, int v, int f) {
			if (u == v) {
				return f;
			}

			for (; checkedTo[u] < edges[u].size(); checkedTo[u]++) {
				Edge e = edges[u].get(checkedTo[u]);
				if (level[e.v] > level[u] && e.w - e.f > 0) {
					int a = dfs(e.v, v, Math.min(f, e.w - e.f));
					if (a != 0) {
						e.f += a;
						edges[e.v].get(e.revIndex).f -= a;

						return a;
					}
				}
			}

			return 0;
		}

		private static class Edge {
//			int u; // from
			int v; // to
			int w; // cost
			int f; // flow
			int revIndex; // index of reverse edge
			boolean revFlag; // flag of reverse edge

			Edge(int v, int w, int re, boolean f) {
//				this.u = u;
				this.v = v;
				this.w = w;
				this.f = 0;
				this.revIndex = re;
				this.revFlag = f;
			}
		}
	}
}
0