[商管] 105 成大資結

[klps50932 (可伊)]

各位好
寫考古的時候遇到好多問題
希望各位大神能夠幫忙解惑QQ

7.
https://i.imgur.com/QVOHCex.jpg
我的想法是a用Prim解，b用Dijkstra解
兩題的時間複雜度都是O(mlogn)
不知道這樣對不對？

5.（3）
https://i.imgur.com/N3ipaKJ.jpg
是指求出一個交集需要多少時間嗎？
因為沒有看過類似的題目
網路上也找不到disjoint set的intersection怎麼求
我能想到只有最暴力的直接比較2個array
花O(n^2)時間

2.
https://i.imgur.com/oPXXNnc.jpg
這題是直接不知道怎麼解QQ

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.74.106.142
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1550911584.A.58B.html
※ 編輯: klps50932 (42.74.106.142), 02/23/2019 16:48:07
→ Dora5566: 考完了喇
推 GlassesKJ: 資管是明天考吧
推 GlassesKJ: 2、job i 需要t單位消耗，獲得定量收入……背包問題？
推 GlassesKJ: 只是這個收入還要減一個損失
推 FRAXIS: 7b 應該是 Minimum bottleneck spanning tree
推 FRAXIS: 5(3) 用 disjoint set + hash 可以嗎？
推 FRAXIS: 2 的遞迴關係應該是 F(t, k) = 只使用前 k 個 job 當
→ FRAXIS: finish time 是 t 時 可以得到的最大 profit
推 TWkobe: Disjoint set 好像leetcode有類似的