結果

問題 No.654 Air E869120
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2021-02-23 17:32:20
言語 Ruby
(3.3.0)
結果
AC  
実行時間 306 ms / 2,000 ms
コード長 2,003 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 24,576 KB
最終ジャッジ日時 2024-09-22 12:42:13
合計ジャッジ時間 8,286 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
12,160 KB
testcase_01 AC 87 ms
12,288 KB
testcase_02 AC 86 ms
12,160 KB
testcase_03 AC 88 ms
12,160 KB
testcase_04 AC 86 ms
12,416 KB
testcase_05 AC 86 ms
12,288 KB
testcase_06 AC 87 ms
12,288 KB
testcase_07 AC 87 ms
12,288 KB
testcase_08 AC 88 ms
12,160 KB
testcase_09 AC 87 ms
12,160 KB
testcase_10 AC 306 ms
24,576 KB
testcase_11 AC 278 ms
21,504 KB
testcase_12 AC 285 ms
22,528 KB
testcase_13 AC 292 ms
23,040 KB
testcase_14 AC 266 ms
21,120 KB
testcase_15 AC 279 ms
21,760 KB
testcase_16 AC 221 ms
15,616 KB
testcase_17 AC 225 ms
15,616 KB
testcase_18 AC 217 ms
15,360 KB
testcase_19 AC 221 ms
15,872 KB
testcase_20 AC 199 ms
13,824 KB
testcase_21 AC 202 ms
14,080 KB
testcase_22 AC 195 ms
13,184 KB
testcase_23 AC 197 ms
13,312 KB
testcase_24 AC 199 ms
13,824 KB
testcase_25 AC 190 ms
12,800 KB
testcase_26 AC 195 ms
13,056 KB
testcase_27 AC 188 ms
12,672 KB
testcase_28 AC 189 ms
12,800 KB
testcase_29 AC 188 ms
12,416 KB
testcase_30 AC 179 ms
12,544 KB
testcase_31 AC 179 ms
12,672 KB
testcase_32 AC 181 ms
12,416 KB
testcase_33 AC 181 ms
12,544 KB
testcase_34 AC 185 ms
12,544 KB
testcase_35 AC 87 ms
12,160 KB
testcase_36 AC 89 ms
12,160 KB
testcase_37 AC 89 ms
12,160 KB
testcase_38 AC 90 ms
12,160 KB
testcase_39 AC 89 ms
12,160 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