推 suhorng:那種做法必須是tree (也就是undirected acyclic graph) 02/09 14:52
→ suhorng:若DAG就照拓樸順序DP 02/09 14:54
→ metalalive:3Q ,topology sort OK, 不過後面的DP作法還不清楚 02/09 15:39
推 suhorng:dst[v] = 1 + max{dst[u] | (v,u)∈E} 02/09 15:43
※ 引述《love5566188 (I'dont kown)》之銘言：
: 小弟自寫的答案,與大家核對看看,若有錯請幫提醒改正
: 5.
: eo 0 1 e2 e1
: e1 1 2 null e2
: e3 0 2 null null
請教multi list 這樣寫是什麼意思呢?
感謝
: 6.
: (a)
: -1 ╱ 0 1 2 ╲
: A = ∣ 3 0 0 ∣
: ╲ 3 6 0 ／
請教 如果沒有邊相連 ex. (2,1) (0,0)
那是矩陣entry要填入 0 還是無限大?
填寫0好像也很合理,這邊不太會分辨題意
: (b)
: 1 ╱ 0 3 3 ╲
: A = ∣ 1 0 4 ∣
: ╲ 2 5 0 ／
: 8.
: (1)自一點作BFS,最後一點稱u
: (2)從u作BFS,最後一點稱v
: (3)u到v即為longest simple path
我原本作法也跟你一樣
做兩次BFS抓acyclic graph 的 最大path
BUT後來發現題目是問 directed acyclic graph
(不是 undirected acylic graph 之類的)
不知道解法是不是相同
我其餘的答案都跟你一樣
3Q
--
No time to pray....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.128.126.145