結果

問題 No.177 制作進行の宮森あおいです！
ユーザー kou6839
提出日時 2015-06-21 00:31:31
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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");
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0