結果

問題 No.654 Air E869120
コンテスト
ユーザー TANIGUCHI Kousuke
提出日時 2021-02-23 17:32:20
言語 Ruby
(3.4.1)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
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