結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー hytkxd
提出日時 2024-05-09 22:14:54
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 2,773 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 178,656 KB
最終ジャッジ日時 2024-12-17 16:32:59
合計ジャッジ時間 49,491 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

#!/usr/local/bin/ruby
class BipartiteMatching
  LEFT,RIGHT=0,1
  def initialize(n,adj,left=nil,right=nil)
    @n,@adj,@left,@right = n,adj,left,right # adj is assumed bipartite.
    @matching_num,@match = nil,nil
  end
  private
  def bipartite
    unless @left
      part = Array.new(2){[]}
      visited = []
      (0...@n).each do |i|
        unless visited[i]
          que = [i]
          visited[i] = LEFT
          part[LEFT].push(i)
          until que.empty?
            v = que.shift
            d1 = visited[v]+1
            @adj[v].each do |w|
              unless visited[w]
                visited[w] = d1
                part[d1%2].push(w)
                que.push(w)
              end
            end
          end
        end
      end
      @left,@right = part
    end
  end
  def altpath(v)
    # return true if alternating path starting from v to be augmented.
    bool = false
    @visited[v] = true
    @adj[v].each do |u|
      w = @match[u]
      if w.nil? || (@visited[w].nil? && altpath(w))
        bool,@match[v],@match[u] = true,u,v
        break
      end
    end
    bool
  end
  public
  def matching
    #kuhn algorithm:
    # Start by unsaturated vertex, find an augmenting path, update the matching.
    # return number of max matching, and the matching list.
    unless @match
      r = 0
      @match = Array.new(@n)
      (0...@n).each do |i|
      unless @match[i]
        @visited = Array.new(@n)
        if altpath(i)
          r+=1
        end
      end
      end
      @matching_num = r
    end
    [@matching_num,@match]
  end
  def min_vertex_cover
    # https://en.wikipedia.org/wiki/K%C5%91nig's_theorem_(graph_theory)
    matching
    bipartite
    @visited = Array.new(@n)
    @cover = Array.new(@n)
    @left.each{@cover[_1]=true}
    @left.each do |i|
      unless @visited[i] || @match[i]
        altcover(i)
      end
    end
    (0...@n).filter_map{_1 if @cover[_1]}
  end
  def altcover(v)
    # v is in A.
    # push to @cover when v is in A but not in altpath, or when v is in B and altpath.
    unless @visited[v]
      @visited[v] = true
      @cover[v] = false
      @adj[v].each do |u|
        unless @visited[u]
          @cover[u] = true
          altcover(@match[u])
        end
      end
    end
  end
end
### END: class BipartiteMatching

class PlayWithNoel
  def initialize(*arg)
    @n,@uv, = arg
  end

  private
  def graph
    @adj=Array.new(@n){Array.new}
    @uv.each{|u,v| @adj[u-1].push(v-1); @adj[v-1].push(u-1)}
  end

  public

  def ans
    graph
    tree = BipartiteMatching.new(@n,@adj)
    cover = tree.min_vertex_cover
    @n-cover.size
  end
end
### END: class PlayWithNoel
iod = STDIN
n = iod.gets.to_i
uv = Array.new(n-1){iod.gets.split.map &:to_i}
puts PlayWithNoel.new(n,uv).ans
exit 0
0