結果

問題 No.177 制作進行の宮森あおいです！
ユーザー autotaker1984autotaker1984
提出日時 2015-07-18 14:23:54
言語 Java21
(openjdk 21)
結果
AC  
実行時間 298 ms / 2,000 ms
コード長 2,727 bytes
コンパイル時間 2,036 ms
コンパイル使用メモリ 78,616 KB
実行使用メモリ 46,988 KB
最終ジャッジ日時 2024-07-08 10:10:29
合計ジャッジ時間 5,863 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 134 ms
41,712 KB
testcase_01 AC 141 ms
42,024 KB
testcase_02 AC 136 ms
41,724 KB
testcase_03 AC 152 ms
41,968 KB
testcase_04 AC 155 ms
42,224 KB
testcase_05 AC 191 ms
43,644 KB
testcase_06 AC 229 ms
45,900 KB
testcase_07 AC 164 ms
42,288 KB
testcase_08 AC 181 ms
42,276 KB
testcase_09 AC 277 ms
46,988 KB
testcase_10 AC 287 ms
46,536 KB
testcase_11 AC 298 ms
46,648 KB
testcase_12 AC 275 ms
46,764 KB
testcase_13 AC 124 ms
41,668 KB
testcase_14 AC 110 ms
41,656 KB
testcase_15 AC 115 ms
41,228 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int W = in.nextInt();
    int N = in.nextInt();
    int[] js = new int[N];
    for( int i = 0; i < N; i++ ) js[i] = in.nextInt();
    int M = in.nextInt();
    int[] cs = new int[M];
    for( int i = 0; i < M; i++ ) cs[i] = in.nextInt();
    
    MaxFlow f = new MaxFlow(2 + M + N);
    for( int i = 0; i < N; i++ ) f.addEdge(0, 1 + i, js[i]);
    for( int i = 0; i < M; i++ ) {
      f.addEdge(1 + N + i, M + N + 1, cs[i]);
      int q = in.nextInt();
      boolean[] bad = new boolean[N];
      for( int j = 0; j < q; j++ ) {
        bad[in.nextInt()-1] = true;
      }
      for( int j = 0; j < N; j++ ) {
        if( !bad[j] ) f.addEdge( 1 + j, 1 + N + i, W );
      }
    }
    int flow = f.run( 0, M+N+1);
//    System.out.println("flow: " + flow);
    if( flow >= W ) {
      System.out.println("SHIROBAKO");
    }else {
      System.out.println("BANSAKUTSUKITA");
    }
  }
}


class Edge {
  int from;
  int to;
  int cap;
  Edge rev;
  public Edge( int from, int to, int cap ) {
    this.from = from;
    this.to = to;
    this.cap = cap;
  }
}

class MaxFlow {
  int N;
  ArrayList<ArrayList<Edge>> g;
  ArrayList<Edge> edges;

  public MaxFlow(int N) {
    this.N = N;
    this.g = new ArrayList<ArrayList<Edge>>();
    this.edges = new ArrayList<Edge>();
    for( int i = 0; i < N; i++ ) {
      this.g.add(new ArrayList<Edge>());
    }
  }

  public void addEdge( int from, int to, int cap ) {
    Edge e1 = new Edge( from, to, cap );
    Edge e2 = new Edge( to, from, 0   );
    e1.rev = e2;
    e2.rev = e1;
    g.get(from).add(e1);
    g.get(to).add(e2);
  }

  public int run( int src, int sink ) {
    int flow = 0;
    while( true ) {
      boolean[] vis = new boolean[N];
      LinkedList<Edge> path = new LinkedList<Edge>();
      boolean b = dfs(vis, path, src, sink );
      if( !b ) break;
      int cap = Integer.MAX_VALUE;
      for( Edge e : path ) cap = Math.min(e.cap,cap);
      flow += cap;
      /*
      System.out.println("cap : " + cap);
      System.out.print("path :" + src);
      */
      for( Edge e : path ) {
        //System.out.print(" " + e.to);
        e.cap -= cap;
        e.rev.cap += cap;
      }
      //System.out.println();
    }
    return flow;
  }

  private boolean dfs(boolean[] vis, LinkedList<Edge> path, int v, int t ) {
    if( v == t ) return true;
    if( vis[v] ) return false;
    vis[v] = true;
    for( Edge e : g.get(v) ) {
      if( !vis[e.to] && e.cap > 0)  {
        path.add(e);
        if( dfs(vis, path, e.to, t) ) {
          return true;
        }
        path.removeLast();
      }
    }
    return false;
  }
}
0