結果

問題 No.177 制作進行の宮森あおいです！
ユーザー uafr_cs
提出日時 2015-09-15 18:14:13
言語 Java
(openjdk 23)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 2,516 bytes
コンパイル時間 2,292 ms
コンパイル使用メモリ 80,064 KB
実行使用メモリ 43,376 KB
最終ジャッジ日時 2024-07-19 06:37:29
合計ジャッジ時間 6,160 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
	
	public static final int INF = Integer.MAX_VALUE / 2 - 1;
	
	public static int dinic(Vertex s, Vertex t) {
		int flow = 0;
		for (int p = 1;; p++) {
			Queue<Vertex> que = new LinkedList<Vertex>();
			s.level = 0;
			s.p = p;
			que.offer(s);

			while (!que.isEmpty()) {
				Vertex v = que.poll();
				v.iter = v.es.size() - 1;
				for (Edge e : v.es)
					if (e.to.p < p && e.cap > 0) {
						e.to.level = v.level + 1;
						e.to.p = p;
						que.offer(e.to);
					}
			}

			if (t.p < p) {
				return flow;
			}

			for (int f; (f = dfs(s, t, INF)) > 0;) {
				flow += f;
			}
		}
	}

	public static int dfs(Vertex v, Vertex t, int f) {
		if (v == t) {
			return f;
		}

		for (; v.iter >= 0; v.iter--) {
			Edge e = v.es.get(v.iter);
			if (v.level < e.to.level && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					e.rev.cap += d;
					return d;
				}
			}
		}

		return 0;
	}

	public static class Vertex {
		ArrayList<Edge> es = new ArrayList<Edge>();
		int level, p, iter;

		void add(Vertex to, int cap) {
			Edge e = new Edge(to, cap), rev = new Edge(this, 0);
			e.rev = rev;
			rev.rev = e;
			es.add(e);
			to.es.add(rev);
		}
	}

	public static class Edge {
		Vertex to;
		Edge rev;
		int cap;

		Edge(Vertex to, int cap) {
			this.to = to;
			this.cap = cap;
		}
	}

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

		final int W = sc.nextInt();
		
		Vertex S = new Vertex();
		Vertex T = new Vertex();
		
		final int N = sc.nextInt();
		int[] Js = new int[N];
		Vertex[] Jv = new Vertex[N];
		for(int i = 0; i < N; i++){
			Js[i] = sc.nextInt();
			Jv[i] = new Vertex();
			S.add(Jv[i], Js[i]);
		}
		
		final int M = sc.nextInt();
		int[] Cs = new int[M];
		Vertex[] Cv = new Vertex[M];
		for(int i = 0; i < M; i++){
			Cs[i] = sc.nextInt();
			Cv[i] = new Vertex();
			Cv[i].add(T, Cs[i]);
		}
		
		for(int i = 0; i < M; i++){
			Set<Integer> set = new HashSet<Integer>();
			
			final int Q = sc.nextInt();
			for(int j = 0; j < Q; j++){
				set.add(sc.nextInt() - 1);
			}
			
			for(int j = 0; j < N; j++){
				if(!set.contains(j)){
					Jv[j].add(Cv[i], INF);
				}
			}
		}
		
		final int OK = dinic(S, T);
		//System.out.println(OK);
		
		System.out.println(OK >= W ? "SHIROBAKO" : "BANSAKUTSUKITA");
		
	}

}
0