結果

問題 No.1541 ゅゅさんのテスト勉強
コンテスト
ユーザー tomerun
提出日時 2021-06-06 20:08:09
言語 Crystal
(1.14.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,959 bytes
コンパイル時間 13,775 ms
コンパイル使用メモリ 295,540 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-23 15:41:28
合計ジャッジ時間 13,420 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = read_line.split.map(&.to_i)
total = m.to_i64 * n
src = n
snk = n + 1
f = Dinic.new(n + 2)
n.times do |i|
  k, c = read_line.split.map(&.to_i)
  f.add_edge(i, snk, c.to_i64)
  if k > 0
    a = read_line.split.map(&.to_i)
    b = read_line.split.map(&.to_i64)
    total += b.sum
    f.add_edge(src, i, b.sum + m)
    k.times do |j|
      f.add_edge(i, a[j] - 1, b[j])
    end
  end
end
puts total - f.calc(src, snk)

# adjacent list
class Dinic
  class Edge
    property :to, :cap, :rev

    def initialize(@to : Int32, @cap : Int64, @rev : Int32)
    end
  end

  getter :g
  @g : Array(Array(Edge))
  @level : Array(Int32)
  @next : Array(Int32)

  def initialize(size : Int32)
    @g = Array.new(size) { Array(Edge).new }
    @level = Array.new(size, -1)
    @next = Array.new(size, 0)
  end

  def add_edge(s : Int32, t : Int32, cap : Int64)
    @g[s] << Edge.new(t, cap, @g[t].size)
    @g[t] << Edge.new(s, 0i64, @g[s].size - 1)
  end

  private def bfs(s)
    @level.fill(-1)
    @level[s] = 0
    que = [s]
    @g.size.times do |i|
      break if i == que.size
      cur = que[i]
      @g[cur].each do |edge|
        if edge.cap > 0 && @level[edge.to] == -1
          @level[edge.to] = @level[cur] + 1
          que << edge.to
        end
      end
    end
  end

  private def dfs(pos : Int32, t : Int32, f : Int64)
    return f if pos == t
    while @next[pos] < @g[pos].size
      e = @g[pos][@next[pos]]
      if e.cap > 0 && @level[pos] < @level[e.to]
        v = dfs(e.to, t, {e.cap, f}.min)
        if v > 0
          e.cap -= v
          @g[e.to][e.rev].cap += v
          return v
        end
      end
      @next[pos] += 1
    end
    return 0i64
  end

  def calc(s : Int32, t : Int32) : Int64
    flow = 0i64
    while true
      bfs(s)
      if @level[t] == -1
        return flow
      end
      @next.fill(0)
      while true
        f = dfs(s, t, Int64::MAX)
        break if f <= 0
        flow += f
      end
    end
  end
end
0