結果

問題 No.654 Air E869120
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2021-02-23 17:32:20
言語 Ruby
(3.3.0)
結果
AC  
実行時間 330 ms / 2,000 ms
コード長 2,003 bytes
コンパイル時間 104 ms
コンパイル使用メモリ 11,972 KB
実行使用メモリ 28,056 KB
最終ジャッジ日時 2023-10-23 18:56:07
合計ジャッジ時間 9,490 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
16,080 KB
testcase_01 AC 83 ms
16,080 KB
testcase_02 AC 83 ms
16,076 KB
testcase_03 AC 82 ms
16,080 KB
testcase_04 AC 82 ms
16,080 KB
testcase_05 AC 83 ms
16,080 KB
testcase_06 AC 89 ms
16,080 KB
testcase_07 AC 89 ms
16,080 KB
testcase_08 AC 87 ms
16,080 KB
testcase_09 AC 86 ms
16,080 KB
testcase_10 AC 330 ms
28,056 KB
testcase_11 AC 290 ms
25,068 KB
testcase_12 AC 308 ms
26,496 KB
testcase_13 AC 317 ms
26,956 KB
testcase_14 AC 285 ms
24,892 KB
testcase_15 AC 311 ms
25,684 KB
testcase_16 AC 237 ms
19,348 KB
testcase_17 AC 241 ms
19,576 KB
testcase_18 AC 233 ms
19,072 KB
testcase_19 AC 234 ms
19,744 KB
testcase_20 AC 216 ms
17,820 KB
testcase_21 AC 218 ms
17,920 KB
testcase_22 AC 214 ms
17,028 KB
testcase_23 AC 215 ms
17,356 KB
testcase_24 AC 215 ms
17,820 KB
testcase_25 AC 204 ms
16,900 KB
testcase_26 AC 208 ms
16,988 KB
testcase_27 AC 202 ms
16,600 KB
testcase_28 AC 209 ms
16,852 KB
testcase_29 AC 200 ms
16,412 KB
testcase_30 AC 196 ms
16,368 KB
testcase_31 AC 194 ms
16,368 KB
testcase_32 AC 193 ms
16,368 KB
testcase_33 AC 194 ms
16,368 KB
testcase_34 AC 194 ms
16,368 KB
testcase_35 AC 81 ms
16,080 KB
testcase_36 AC 81 ms
16,080 KB
testcase_37 AC 81 ms
16,080 KB
testcase_38 AC 80 ms
16,080 KB
testcase_39 AC 82 ms
16,080 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

INF = 10 ** 15
def _min(a,b); a < b ? a : b; end
def max_flow(s,t)
  flow = 0
  while level = levelize(s,t)
    active = Array.new(G.size, 0)
    while f = find_flow(s, t, level, active)
      flow += f
    end
  end
  flow
end

def find_flow(s, t, level, active)
  flow = Array.new(G.size)
  parent = Array.new(G.size)
  parent[s] = s
  flow[s] = INF
  u = s
  until u == t
    if (j = active[u]) >= G[u].size
      break if u == s
      u = parent[u]
      active[u] += 1
    else
      e = G[u][j]
      if e.cap > 0 && level[e.to] < level[u]
        parent[e.to] = u
        flow[e.to] = _min(flow[u], e.cap)
        u = e.to
      else
        active[u] += 1
      end
    end
  end
  return nil if u == s
  u, f = s, flow[t]
  until u == t
    fwd = G[u][active[u]]
    rev = G[fwd.to][fwd.rev]
    fwd.cap -= f
    rev.cap += f
    u = fwd.to
  end
  return f
end
def levelize(s,t)
  level = Array.new(G.size, G.size * 2)
  level[t] = 0
  q = [t]
  until q.empty?
    u = q.shift
    d = level[u]
    next if u == s
    G[u].each do |e|
      if G[e.to][e.rev].cap > 0 && level[e.to] > d + 1
        level[e.to] = d + 1
        q << e.to
      end
    end
  end
  level[s] = G.size if level[s] <= G.size
  level[s] <= G.size ? level : nil
end

Line = Struct.new(:id, :u, :v, :s, :t, :w) do
  def from; 2 * id; end
  def to; 2 * id + 1; end
end

N,M,d = gets.split.map(&:to_i)
S = 2 * M; T = 2 * M + 1;
G = Array.new(2 * M + 2){ [] }
class << G
  Edge = Struct.new(:to, :cap, :rev)
  def dir_to(from, to, cap)
    fwd, rev = self[from].size, self[to].size
    self[from] << Edge.new(to, cap, rev)
    self[to] << Edge.new(from, 0, fwd)
    self
  end
end

L = M.times.map{|id| u,v,s,t,w = gets.split.map(&:to_i); Line.new(id,u,v,s,t,w) }
L.each do |l|
  G.dir_to(l.from, l.to, l.w)
  G.dir_to(S, l.from, INF) if l.u == 1
  G.dir_to(l.to, T, INF) if l.v == N
end
L.each do |l|
  L.each do |r|
    next if l.v != r.u
    G.dir_to(l.to, r.from, INF) if l.t + d <= r.s
  end
end

puts max_flow(S, T)
0