[理工] 成大104程設

看板Grad-ProbAsk作者 (軒昂)時間9年前 (2016/02/24 01:27), 9年前編輯推噓2(2推 0噓 11→)
留言13則, 3人參與, 最新討論串1/2 (看更多)
http://exam.lib.ncku.edu.tw/showfile.php?file=exam/%E7%A2%A9%E5%A3%AB%E7%8F%AD%E8%80%83%E8%A9%A6/%E9%9B%BB%E6%A9%9F%E8%B3%87%E8%A8%8A%E5%AD%B8%E9%99%A2/%E9%9B%BB%E6%A9%9F%E8%B3%87%E8%A8%8A%E5%AD%B8%E9%99%A2-%E8%B3%87%E8%A8%8A%E8%81%AF%E6%8B%9B/104%E8%B3%87%E8%A8%8A%E5%B7%A5%E7%A8%8B%E5%AD%B8%E7%B3%BB%E3%80%81%E9%86%AB%E5%AD%B8%E8%B3%87%E8%A8%8A%E7%A0%94%E7%A9%B6%E6%89%80%E8%81%AF%E6%8B%9B/209_%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88.pdf 3(a). for(int k=0;k<n;k++) if(!found[k] && distance[k]<min) { min = distance[k]; minpos = k; } (b) for(int i=0;i<n;i++) for(int u=0;u<n;u++) 5. 16375 6.Theta(n^1/2*lgn) 7.有負環所以no solution 這幾題這樣寫不知道對不對 希望會的人指點一下 還有 第四題 不知道怎麼下手QQ 感謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 119.14.194.59 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1456248475.A.8F9.html
→
02/24 01:45, , 1F
4.找拓撲排序,再從與最前的點相連的邊開始依序作bellm
02/24 01:45, 1F
→
02/24 01:45, , 2F
an algo.中的 relax
02/24 01:45, 2F
→
02/24 01:47, , 3F
dfs找拓撲花O(V+E),而bellman ford只要知道shortest p
02/24 01:47, 3F
→
02/24 01:47, , 4F
ath上邊的正確的relax順序就只需O(E)
02/24 01:47, 4F
→
02/24 01:54, , 5F
3.b i,u變數好像要對調比較好, 7,我算似乎有解
02/24 01:54, 5F
→
02/24 08:42, , 6F
7我算好像有負cycle@@ 不確定
02/24 08:42, 6F
感謝回答~ 突然發現3.b題目的k是從2開始 這樣不是就只有做n-2次relax 不是應該要n-1次嗎? 7.我畫圖出來發現v1,v4,v5有負cycle ※ 編輯: lemonsheep (119.14.194.59), 02/24/2016 11:19:13
→
02/24 12:43, , 7F
7.的確有負cycle,sor
02/24 12:43, 7F
→
02/24 12:44, , 8F
3.b 他把k=1的情況在initial時候作了吧
02/24 12:44, 8F
推
02/24 13:06, , 9F
想順便請問一下第七題，這題用負cycle,即可判斷，
02/24 13:06, 9F
→
02/24 13:06, , 10F
那v0到各點的最短距離是不是沒求也沒關係，我看解
02/24 13:06, 10F
→
02/24 13:06, , 11F
答都有求說，感謝大大
02/24 13:06, 11F
→
02/24 13:10, , 12F
有解給解集用的吧, 配分重時最好也列一下
02/24 13:10, 12F
推
02/24 13:13, , 13F
好的，謝謝你！！
02/24 13:13, 13F
‣ 更多 lemonsheep 的文章
文章代碼(AID): #1Mp9QRZv (Grad-ProbAsk)
‣ 更多 lemonsheep 的文章
文章代碼(AID): #1Mp9QRZv (Grad-ProbAsk)