作者darrenlee1 (darrenleeleelee)
看板Grad-ProbAsk
标题[理工] 108交大资演13题
时间Sat Jan 22 11:23:24 2022
https://i.imgur.com/PtNhc0R.jpg
想问一下这题题目是在说什麽呢，那个数学式有点看不懂，27就做不出来。
28、29了解fibonacci 和binary heap就做得出来。
但27真的没想法…
Ans:
27.E
28.ACDE
29.D
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.43.163.67 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1642821806.A.CF7.html
1F：推 VF84: 我想不太到好的解释，但我认为它跟 Prim 在基本的精神上有 01/22 13:44
2F：→ VF84: 些类似。你或许可以试着从这点下手 01/22 13:44
3F：推 kronze7109: 算式讲的是magic order的定义 01/23 22:18
4F：→ kronze7109: 我的理解是 01/23 22:19
5F：→ kronze7109: V1是演算法选出来的第一个点 01/23 22:19
6F：→ kronze7109: V2是第二个点，依此类推 01/23 22:19
7F：→ kronze7109: 01/23 22:19
8F：→ kronze7109: 选定V1後会将各点更新key值 01/23 22:19
9F：→ kronze7109: 也就是key(v2)=w(v1,v2)其余的点也是一样 01/23 22:19
10F：→ kronze7109: 新的一轮挑出key值最大的点当V2 01/23 22:19
11F：→ kronze7109: 再更新其余的点 01/23 22:19
12F：→ kronze7109: key(v3)=key(v3)+w(v2,v3)=w(v1,v3)+w(v2,v3) 01/23 22:19
13F：→ kronze7109: 依此类推 01/23 22:19
14F：→ kronze7109: 每个key值就会变成式子那样 01/23 22:19
15F：→ kronze7109: 如此就可以求出magic order了 01/23 22:19
16F：→ kronze7109: 有点像是Dijkstra的感觉 01/23 22:19
17F：→ kronze7109: 如果还是不懂欢迎指教 01/23 22:19
18F：→ kronze7109: 有错误的地方也请各位大神鞭策 01/23 22:19