🐸
[EDPC G] Longest Path
有向グラフのパスの最長を求める問題。
問題を要約する
- 有向グラフを一筆で辿ったときの最長は？
- 辺の本数を答える
たとえば A → B だと 1 になる。
例1で問題を理解する
1 → 3 → 2 → 4 と一筆で辿るといちばん長くなるので答えは 3 になる。
解法
- DFS で任意の頂点から進めた場合の最長を求めることができるようにしておく
- それをすべての頂点から開始して、その中で最長を求める
解説の模範解答(C++)風の実装 (AC)
277 ms
N, M = gets.split.collect(&:to_i) # => [4, 5]
XY = M.times.collect { gets.split.collect(&:to_i).collect(&:pred) }
XY # => [[0, 1], [0, 2], [2, 1], [1, 3], [2, 3]]
# 有向グラフの作成
G = Array.new(N) { [] }
XY.each { |from, to| G[from] << to }
G # => [[1, 2], [3], [1, 3], []]
# DP というよりメモ化のためにある感じ
dp = Array.new(N)
# from から開始したときの最長距離を返す
dfs = -> from {
if dp[from]
return dp[from] # これがないと TLE になる
end
dist = 0
G[from].each do |to|
if dist < dfs[to] + 1
dist = dfs[to] + 1
end
end
dp[from] = dist
}
# すべての頂点から開始して最長距離を調べる
dist = 0
N.times.each do |v|
if dist < dfs[v]
dist = dfs[v]
end
end
p dist # => 3
あまり DP という感じがしないが、このようなメモ化も DP の一種らしい。メモ化しないと TLE になる。
リファクタリング後 (AC)
227 ms
N, M = gets.split.collect(&:to_i) # => [4, 5]
XY = M.times.collect { gets.split.collect(&:to_i).collect(&:pred) }
G = Array.new(N) { [] }
XY.each { |from, to| G[from] << to }
dp = Array.new(N)
dfs = -> from { dp[from] ||= G[from].collect { |to| dfs[to].next }.max || 0 }
p N.times.collect { |from| dfs[from] }.max # => 3
Discussion