結果

問題 No.177 制作進行の宮森あおいです！
ユーザー threepipes_s
提出日時 2015-05-19 00:46:43
言語 Java
(openjdk 23)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 4,317 bytes
コンパイル時間 3,225 ms
コンパイル使用メモリ 88,948 KB
実行使用メモリ 44,116 KB
最終ジャッジ日時 2024-07-06 05:32:17
合計ジャッジ時間 5,181 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
public class Main {
    public static int[][] cap;
    public static BitSet used;
    public static int n;
    public static int m;
    public static void main(String[] args) throws NumberFormatException,
    IOException {
        ContestScanner in = new ContestScanner();
        int w = in.nextInt();
        n = in.nextInt();
        int[] J = new int[n];
        for(int i=0; i<n; i++) J[i] = in.nextInt();
        m = in.nextInt();
        int[] C = new int[m];
        for(int i=0; i<m; i++) C[i] = in.nextInt();
        Node[] node = new Node[1 + n + m + 1];
        int nodes = 2 + n + m;
        for(int i=0; i<nodes; i++){
            node[i] = new Node(i);
        }
        cap = new int[nodes][nodes];
        for(int i=0; i<n; i++){
            node[0].createEdge(node[1+i]);
            node[1+i].createEdge(node[0]);
            cap[0][1+i] = J[i];
        }
        // 1: source; 1+i: 原画; 1+n+i: 監督; 1+n+m: sink
        for(int i=0; i<m; i++){
            int q = in.nextInt();
            BitSet bs = new BitSet(n);
            for(int j=0; j<q; j++){
                bs.set(in.nextInt()-1);
            }
            for(int j=bs.nextClearBit(0); j<n; j=bs.nextClearBit(j+1)){
                // 1+j -> 1+n+j にJ[i]をはる
                node[1+j].createEdge(node[1+n+i]);
                node[1+n+i].createEdge(node[1+j]);
                cap[1+j][1+n+i] = J[j];
            }
            node[1+n+i].createEdge(node[1+n+m]);
            node[1+n+m].createEdge(node[1+n+i]);
            cap[1+n+i][1+n+m] = C[i];
        }
        int res = 0;
        while(true){
            used = new BitSet(nodes);
//          used.set(0);
            int flow = dfs(node[0], 10000000);
            if(flow == 0) break;
            res += flow;
        }
        System.err.println(res);
        System.out.println(res >= w ? "SHIROBAKO" : "BANSAKUTSUKITA");
    }
    
    public static int dfs(Node node, int f){
        if(node.id == 1 + n + m) return f;
        if(used.get(node.id)) return 0;
        used.set(node.id);
        for(Node nd: node.edge){
            if(cap[node.id][nd.id] > 0){
                int flow = dfs(nd, Math.min(f, cap[node.id][nd.id]));
                if(flow > 0){
                    // ここが機能しているか怪しい
//                  if(node.id > nd.id)
                        cap[nd.id][node.id]+=flow;
//                  else 
                        cap[node.id][nd.id]-=flow;
                    return flow;
                }
            }
        }
        return 0;
    }
}
class Node{
    int id;
    int sink;
    ArrayList<Node> edge = new ArrayList<Node>();
    public Node(int id) {
        this.id = id;
    }
    public void createEdge(Node node) {
        edge.add(node);
    }
}
class MyComp implements Comparator<int[]> {
    final int idx;
    public MyComp(int idx){
        this.idx = idx;
    }
    public int compare(int[] a, int[] b) {
        return a[idx] - b[idx];
    }
}
class Reverse implements Comparator<Integer> {
    public int compare(Integer arg0, Integer arg1) {
        return arg1 - arg0;
    }
}
class ContestWriter {
    private PrintWriter out;
    public ContestWriter(String filename) throws IOException {
        out = new PrintWriter(new BufferedWriter(new FileWriter(filename)));
    }
    public ContestWriter() throws IOException {
        out = new PrintWriter(System.out);
    }
    public void println(String str) {
        out.println(str);
    }
    
    public void println(Object obj) {
        out.println(obj);
    }
    public void print(String str) {
        out.print(str);
    }
    
    public void print(Object obj) {
        out.print(obj);
    }
    public void close() {
        out.close();
    }
}
class ContestScanner {
    private BufferedReader reader;
    private String[] line;
    private int idx;
    public ContestScanner() throws FileNotFoundException {
        reader = new BufferedReader(new InputStreamReader(System.in));
    }
    public ContestScanner(String filename) throws FileNotFoundException {
        reader = new BufferedReader(new InputStreamReader(new FileInputStream(
                filename)));
    }
    public String nextToken() throws IOException {
        if (line == null || line.length <= idx) {
            line = reader.readLine().trim().split(" ");
            idx = 0;
        }
        return line[idx++];
    }
    
    public String readLine() throws IOException{
        return reader.readLine();
    }
    public long nextLong() throws IOException, NumberFormatException {
        return Long.parseLong(nextToken());
    }
    public int nextInt() throws NumberFormatException, IOException {
        return (int) nextLong();
    }
    public double nextDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(nextToken());
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0