結果

問題 No.177 制作進行の宮森あおいです！
ユーザー kou6839kou6839
提出日時 2015-06-21 00:31:31
言語 Java21
(openjdk 21)
結果
AC  
実行時間 260 ms / 2,000 ms
コード長 2,215 bytes
コンパイル時間 1,910 ms
コンパイル使用メモリ 79,752 KB
実行使用メモリ 43,640 KB
最終ジャッジ日時 2024-07-07 15:23:54
合計ジャッジ時間 5,191 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
41,424 KB
testcase_01 AC 131 ms
41,400 KB
testcase_02 AC 120 ms
40,976 KB
testcase_03 AC 147 ms
41,720 KB
testcase_04 AC 148 ms
41,576 KB
testcase_05 AC 164 ms
42,192 KB
testcase_06 AC 187 ms
42,640 KB
testcase_07 AC 149 ms
42,024 KB
testcase_08 AC 165 ms
42,064 KB
testcase_09 AC 222 ms
43,384 KB
testcase_10 AC 225 ms
43,276 KB
testcase_11 AC 260 ms
43,640 KB
testcase_12 AC 223 ms
43,300 KB
testcase_13 AC 114 ms
41,152 KB
testcase_14 AC 117 ms
40,868 KB
testcase_15 AC 120 ms
41,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;

class MaximumFlow {
	private ArrayList<Edge>[] G;
	private boolean[] used;
	
	public 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;
		}
	}
	
	public MaximumFlow(int v){
		used = new boolean[v];
		G = new ArrayList[v];
		for(int i=0;i<v;i++){
			G[i]=new ArrayList<>();
		}
	}	
	
	public void addEdge(int from,int to, int cap){
		G[from].add(new Edge(to, cap, G[to].size()));
		G[to].add(new Edge(from, 0, G[from].size()-1));
	}
	
	private int dfs(int v, int t, int f){
		if(v==t) return f;
		used[v]=true;
		for(int i=0;i<G[v].size();i++){
			Edge edge = G[v].get(i);
			
			if(!used[edge.to] && edge.cap>0){
				int d = dfs(edge.to,t,Math.min(f,edge.cap));
				
				if(d>0){
					edge.cap-=d;
					G[edge.to].get(edge.rev).cap += d;
					return d;
				}
			}
		}
		
		return 0;
	}
	
	public int maxFlow(int s,int t){
		int flow = 0;
		for(;;){
			Arrays.fill(used, false);
			int f = dfs(s, t, Integer.MAX_VALUE);
			
			if(f==0) return flow;
			flow+=f;
		}
	}
}
public class Main {
    public static void main(String[] args){
        // TODO 自動生成されたメソッド・スタブ
    	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();
    	}
    	
    	MaximumFlow MF = new MaximumFlow(N+M+2);
    	 for (int i = 0; i < N; i++) {
              MF.addEdge(N + M, i, J[i]);
          }
          for (int j = 0; j < M; j++) {
              MF.addEdge(N + j, N + M + 1, C[j]);
          }
    	for(int i=0;i<M;i++){
    		int q = sc.nextInt();
    		boolean[] hate = new boolean[N];
    		for(int j=0;j<q;j++){
    			hate[sc.nextInt()-1]=true;
    		}
    		for(int j=0;j<N;j++){
    			if(!hate[j]){
    				MF.addEdge(j, N+i, J[j]);
    			}
    		}
    	}
    	
    	int v = MF.maxFlow(N+M, N+M+1);
    	if(v>=W){
    		System.out.println("SHIROBAKO");
    	}else{
    		System.out.println("BANSAKUTSUKITA");
    	}
    }
}
0