結果

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