Submission #2417043

---

Source Code Expand

# 行先, 容量, 逆辺
Edge = Struct.new(:to, :cap, :rev)

# Ford-Fulkerson 法で最大流を解く
class FordFulkerson
  def initialize(n)
    @G = Array.new(n){[]} # グラフの隣接リスト表現
    @used = Array.new(n)  # DFS で既に調べたか
  end
  
  # from -> to へ向かう容量 cap の辺をグラフに追加
  def add_edge(from, to, cap)
    @G[from] << Edge.new(to, cap, @G[to].size)
    @G[to]   << Edge.new(from, 0, @G[from].size - 1)
  end
  
  # 増加パスを DFS で探索
  def dfs(v, t, f)
    return f if v == t
    @used[v] = true
    @G[v].each do |e|
      if !@used[e.to] && e.cap > 0
        d = dfs(e.to, t, [f, e.cap].min)
        if d > 0
          e.cap -= d
          @G[e.to][e.rev].cap += d
          return d
        end
      end
    end
    0
  end
  
  # s から t への最大流を計算
  def max_flow(s, t)
    flow = 0
    loop do
      @used.fill(false)
      f = dfs(s, t, Float::INFINITY)
      return flow if f == 0
      flow += f
    end
  end
end

N, G, E = gets.split.map(&:to_i)
p = gets.split.map(&:to_i)
ab = Array.new(E) { gets.split.map(&:to_i) }

S, T = 0, N
ff = FordFulkerson.new(N+1)
ab.each do |a, b|
  ff.add_edge(a, b, 1)
  ff.add_edge(b, a, 1)
end
p.each do |x|
  ff.add_edge(x, T, 1)
end
puts ff.max_flow(S, T)

Submission Info

Judge Result