作者klps50932 (可伊)
看板Grad-ProbAsk
標題[商管] 105 成大資結
時間Sat Feb 23 16:46:21 2019
各位好
寫考古的時候遇到好多問題
希望各位大神能夠幫忙解惑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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1550911584.A.58B.html
※ 編輯: klps50932 (42.74.106.142), 02/23/2019 16:48:07
1F：→ Dora5566: 考完了喇 02/23 17:48
2F：推 GlassesKJ: 資管是明天考吧 02/23 18:33
3F：推 GlassesKJ: 2、job i 需要t單位消耗，獲得定量收入……背包問題？ 02/23 18:35
4F：推 GlassesKJ: 只是這個收入還要減一個損失 02/23 19:06
5F：推 FRAXIS: 7b 應該是 Minimum bottleneck spanning tree 02/23 21:48
6F：推 FRAXIS: 5(3) 用 disjoint set + hash 可以嗎？ 02/23 21:55
7F：推 FRAXIS: 2 的遞迴關係應該是 F(t, k) = 只使用前 k 個 job 當 02/23 22:04
8F：→ FRAXIS: finish time 是 t 時 可以得到的最大 profit 02/23 22:04
9F：推 TWkobe: Disjoint set 好像leetcode有類似的 02/25 11:04