Re: [核對] [軟體]-師大100-資工
看板Grad-ProbAsk作者love5566188 (I'dont kown)時間12年前 (2012/02/11 15:13)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/3 (看更多)
※ 引述《metalalive (想玩音樂)》之銘言：
: ※ 引述《love5566188 (I'dont kown)》之銘言：
: : 小弟自寫的答案,與大家核對看看,若有錯請幫提醒改正
: : 5.
: : eo 0 1 e2 e1
: : e1 1 2 null e2
: : e3 0 2 null null
: 請教multi list 這樣寫是什麼意思呢?
: 感謝
每個邊依序往下找與點該對應點有相接的邊,不可往上找
＿＿＿＿
∣ ＿ │＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
↓ ↓ ∣ ∣
e0:邊(0,1) ∣0∣1∣與0有相接的邊(e2) ∣與1有相接的邊(e1)
e1:邊(1,2) ∣1∣2∣因下面沒有與1相接的邊所以為null∣與2有相接的邊(e2)
e2:邊(0,2) ∣0∣2∣null ∣null
: : 6.
: : (a)
: : -1 ╱ 0 1 2 ╲
: : A = ∣ 3 0 0 ∣
: : ╲ 3 6 0 ／
: 請教 如果沒有邊相連 ex. (2,1) (0,0)
: 那是矩陣entry要填入 0 還是無限大?
: 填寫0好像也很合理,這邊不太會分辨題意
我想改一下答案,改用沒有邊想連用無限大
因為我剛看題目直覺只想到離散的鄰接矩陣所以用0
再看一下題目求第一行就說求shortest path,所以讓我想到shortest path algo.
都用無窮大,所以如果出現是求path的話我會用無窮大(因為不可能兩點之間距離
是0而沒連接),寫過的題目大部分答案是用無窮大,但也有出現過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
這題沒看清楚題目抱歉,所以不能用兩次BFS來求,用Topology來做就可以了
(1)找沒有indegree的點u加入T裡面
(2)刪除與u相連的邊重複(1)動作
(3)最後所加入的點稱v,而u到v之path即longest path
我想問一下同樣這份師大100的計系第四題,答案是(a)1450ps(b)40/29
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 175.98.50.200
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：