結果

問題 No.119 旅行のツアーの問題
ユーザー gigurururugigurururu
提出日時 2015-02-19 21:10:49
言語 Ruby
(3.3.0)
結果
AC  
実行時間 91 ms / 5,000 ms
コード長 2,297 bytes
コンパイル時間 46 ms
コンパイル使用メモリ 11,408 KB
実行使用メモリ 16,600 KB
最終ジャッジ日時 2023-08-23 09:15:28
合計ジャッジ時間 3,168 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 83 ms
15,236 KB
testcase_01 AC 88 ms
15,756 KB
testcase_02 AC 86 ms
15,184 KB
testcase_03 AC 81 ms
15,280 KB
testcase_04 AC 78 ms
15,296 KB
testcase_05 AC 83 ms
15,468 KB
testcase_06 AC 90 ms
16,600 KB
testcase_07 AC 79 ms
15,044 KB
testcase_08 AC 78 ms
15,244 KB
testcase_09 AC 78 ms
15,156 KB
testcase_10 AC 78 ms
15,284 KB
testcase_11 AC 80 ms
15,304 KB
testcase_12 AC 80 ms
15,144 KB
testcase_13 AC 80 ms
15,152 KB
testcase_14 AC 84 ms
15,388 KB
testcase_15 AC 82 ms
15,152 KB
testcase_16 AC 87 ms
16,064 KB
testcase_17 AC 83 ms
15,332 KB
testcase_18 AC 85 ms
15,132 KB
testcase_19 AC 80 ms
15,040 KB
testcase_20 AC 86 ms
15,936 KB
testcase_21 AC 90 ms
16,444 KB
testcase_22 AC 91 ms
16,216 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

# グラフの最大フローを求める
class MaxFlow
  def initialize
    @node={}#Hash.new{|h,k|h[k]=[]}
  end

  # ノード追加（外から呼ぶ必要なし）
  def add_node(name)
    @node[name]||=Hash.new{0}
  end

  # エッジ追加
  # costは整数でないと計算できない（INFに当たる値を入れたいときは十分大きい整数にする）
  def add_edge(src,dst,cost)
    add_node(src)
    add_node(dst)
    @node[src][dst]=cost
  end

  # srcからdstの最大フロー時の流量のグラフを以下の形式のハッシュで返す
  # (YAML形式で示す)
  # --
  # [src1]:
  #   [dst1]: [src1->dst1 cost]
  #   [dst2]: [src1->dst2 cost]
  #   [dst3]: [src1->dst3 cost]
  # [src2]:
  #   [dst1]: [src2->dst1 cost]
  #   [dst2]: [src2->dst2 cost]
  #   [dst3]: [src2->dst3 cost]
  def maxflowgraph(src,dst)
    residual=Hash[@node.map{|k,v|[k,v.dup]}]
    while true
      # srcからdstへのパスを幅優先探索
      #p residual
      pre={}
      q=[src]
      while q[0] && !pre[dst]
        sr=q.shift
        residual[sr]&&residual[sr].each{|d,c|
          pre[d]||=(q << d;sr)
        }
      end
      # dstへのパスが見つからなくなったら終了
      break if !pre[dst]
      path=[]
      ds=dst
      co=residual.values.flat_map(&:values).max
      # パスを経路復元し、そのパスの流量を求める
      while ds!=src
        #p ds
        sr=pre[ds]
        co=[residual[sr][ds],co].min
        path.unshift [sr,ds]
        ds=sr
      end
      # 元のグラフから流量を引いた残余グラフを求める
      path.each{|s,d|
        residual[s][d]-=co
        if residual[s][d]==0
          residual[s].delete(d)
        end
        residual[d][s]+=co
      }
    end
    Hash[@node.map{|k,v|[k,Hash[v.map{|d,c|[d,c-residual[k][d]]}]]}]
  end
  # srcからdstの最大フロー時の流量を返す
  def maxflow(src,dst)
    graph=maxflowgraph(src,dst)
    graph[src]?graph[src].values.inject(:+):0
  end
end

def g;gets.split.map(&:to_i)end
sum=0
mf=MaxFlow.new
INF=1000000
g[0].times{|i|
  b,c=g
  sum+=b+c
  mf.add_edge(:src,:"b#{i}",b)
  mf.add_edge(:"b#{i}",:"c#{i}",INF)
  mf.add_edge(:"c#{i}",:sink,c)
}
g[0].times{
  d,e=g
  mf.add_edge(:"b#{d}",:"c#{e}",INF)
}
p sum-mf.maxflow(:src,:sink)
0