Submission #182228

---

Source Code Expand

class Graph
  MAX_FLOW = 1_000_000

  attr_reader :vertices

  def initialize(n)
    @vertices = Array.new(n).map { |_| [] }
  end

  public
  def add_edge!(u, v, cap)
    edge = Edge.new(v, cap)
    edge_rev = Edge.new(u, 0)
    edge.match edge_rev
    edge_rev.match edge
    @vertices[u].push edge
    @vertices[v].push edge_rev
  end

  def dfs(from, to, flow)
    return flow if from == to
    @used[from] = true
    @vertices[from].each { |e|
      if not @used[e.to] and e.cap > 0
        d = dfs(e.to, to, [flow, e.cap].min)
        if d > 0
          e.cap -= d
          e.reverse.cap += d
          return d
        end
      end
    }
    0
  end

  def max_flow(from, to)
    flow = 0
    loop {
      @used = Array.new(@vertices.size, false)
      f = dfs(from, to, MAX_FLOW)
      break if f == 0
      flow += f
    }
    flow
  end
end

class Edge
  attr_reader :to, :cap, :reverse
  attr_writer :cap

  def initialize(to, cap)
    @to = to
    @cap = cap
  end

  def match(match_edge)
    @reverse = match_edge
  end
end

graph = Graph.new(110)
n,_,e = gets.split.map(&:to_i)
gets.split.map(&:to_i).map { |marked|
  graph.add_edge! marked,n,1
}
(0...e).each { |_|
  a,b = gets.split.map(&:to_i)
  graph.add_edge! a,b,1
  graph.add_edge! b,a,1
}
puts graph.max_flow 0,n

Submission Info

Judge Result