結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー sca1l
提出日時 2017-11-16 00:31:01
言語 Ruby
(3.4.1)
結果
AC  
実行時間 468 ms / 2,000 ms
コード長 1,728 bytes
コンパイル時間 450 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2024-11-25 04:10:47
合計ジャッジ時間 4,299 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:2: warning: parentheses after method name is interpreted as an argument list, not a decomposed argument
Main.rb:54: warning: mismatched indentations at 'end' with 'if' at 51
Main.rb:48: warning: assigned but unused variable - q
Main.rb:76: warning: literal in condition
Syntax OK

ソースコード

diff # 

#dfsするやつ
def dfs (graph, used, from, sink, flow)
  return flow if from == sink
  used[from] = true
  
  graph[from].each{|edge|
    #edgeのtoがdfs済み or edgeのcapが0以下のときは次
    next if used[edge[0]] || (edge[1]<=0)
    
    #flowとedgeのcapの小さい方をfminに入れている
    #fmin = edge[1]
    #fmin = flow if fmin > flow
    
    #dfsを投げる。流せる分が返ってくる。
    d = dfs(graph, used, edge[0], sink, [edge[1],flow].min)
    
    #流した分capを減らす。流した分逆流させる事ができるので、逆辺のcapを流した分増やす。
    if d > 0 then
      #edgeのcap
      edge[1] -= d
      #グラフのedgeのtoの逆辺(rev)のcap
      graph[edge[0]][edge[2]][1] += d
      return d
    end
  }
  return 0
end

w = gets.to_i
n = gets.to_i
j = gets.split.map &:to_i
m = gets.to_i
c = gets.split.map &:to_i

#
inf = 100000000
#
source = 0
sink = n+m+1
#n個,それぞれに[to,cap,rev]を追加していく
graph = (n+m+2).times.map{[]}
#調べたか
used = Array.new(n+m+2, false)

#addedge
x = m.times.map{|i|
  dame = Array.new(n, false)
  q,*x = gets.split.map &:to_i
  x.each{|k|dame[k-1] = true}
  n.times{|j|
    if !dame[j] then
	  graph[j+1]<<[n+i+1,inf,graph[n+i+1].size]
      graph[n+i+1]<<[j+1,0,graph[j+1].size-1]
	end
  }
}

#
n.times{|i|
  graph[source]<<[i+1,j[i],graph[i+1].size]
  graph[i+1]<<[source,0,graph[source].size-1]
}
#
m.times{|i|
  graph[n+i+1]<<[sink,c[i],graph[sink].size]
  graph[sink]<<[n+i+1,0,graph[n+i+1].size-1]
}

#fordFulkerson
flow = 0
while 1
  (n+m+2).times{|i| used[i]=false}
  f = dfs(graph, used, source, sink, inf)
  break if f==0
  flow += f
end

puts (flow>=w)?'SHIROBAKO':'BANSAKUTSUKITA'
0