more..

 

$Inf=999999999999999
class Pair
  include Comparable
  def initialize(first=0, second=0)
    @first, @second = first, second
  end
  def to_s()
    "(%d, %d)" % [first, second]
  end
  attr_reader :first, :second
end

class Network
  def initialize()
    @net=Hash.new(nil)
  end
  def plusedge(s,e,value)
    @net[s]=@net[s] || Hash.new(nil)
    @net[s][e]=value
  end
  def add(s, e, value)
    plusedge(s,e,value)
    plusedge(e,s,value)
  end
  attr_accessor:net
  def dup
    Marshal::load(Marshal.dump(self))
  end
end
class Maxflow
  def augment(pos, ed, m=$Inf)        
    return false if (@check & (1<<pos))!=0    
    @check ^= (1<<pos)
    if pos==ed :
      @m=m;
      return true
    else
      @G.net[pos].each do |to, val|              
        next if(val==0)        
        @path[to]=pos
        return true if(augment(to, ed, m>val ? val : m))    
      end
    end    
    @check ^= (1<<pos)
    false
  end

  def fordfulkerson(ed, t)
    ret=0      
    @G=t.dup
    while(augment(1,ed)) do      
      @check=0
      pos=ed
      ret+=@m
      while(pos!=1) do
        prev=@path[pos].to_i
        @G.net[prev][pos]-=@m
        @G.net[pos][prev]+=@m
        pos=prev
      end
    end    
    ret
  end
  def initialize()
      @check=0
      @path=[]
  end
end

def input
  ret=Network.new
  inf=File.open("worldwar.in","r")
  inf.readline=~/(\d+)\s(\d+)/
  $n, $m = $1.to_i, $2.to_i

  $m.times{ inf.readline=~/(\d+)\s+(\d+)\s+(\d+)/
    ret.add($1.to_i, $2.to_i, $3.to_i)
  }
  ret
end

#실행 부분

graph=input
algo=Maxflow.new
ans=$Inf
2.upto($n) { |i| t=algo.fordfulkerson(i,graph);
  ans=t if ans > t
}

File.open("worldwar.out","w").puts ans

전혀 루비스럽지 않은 코드 ... orz

많이 느립니다. 다시 구현할 생각입니다.

이올린에 북마크하기(0) 이올린에 추천하기(0)