結果

問題 No.177 制作進行の宮森あおいです！
ユーザー Grenache
提出日時 2016-06-09 21:29:35
言語 Java
(openjdk 23)
結果
AC  
実行時間 214 ms / 2,000 ms
コード長 3,434 bytes
コンパイル時間 3,938 ms
コンパイル使用メモリ 81,208 KB
実行使用メモリ 54,368 KB
最終ジャッジ日時 2024-10-09 06:48:26
合計ジャッジ時間 7,586 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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