作者aa871220 (怪人干怪事)
看板Grad-ProbAsk
标题[理工] 107台大 资演 minimax path
时间Mon Jan 11 20:13:29 2021
https://imgur.com/T8kbefI
我可以理解由dijkstra修改relax function 能得到这题的结果
正确性也想得出来
但是一开始解题想到的是用同样模板的Prim's algo以求MST
目前想不到怎麽推翻之前的想法= =
想请教一下有没有反例会使得Prim是错误的
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.136.219 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1610367211.A.73D.html
※ 编辑: aa871220 (140.113.136.219 台湾), 01/11/2021 20:15:23
※ 编辑: aa871220 (140.113.136.219 台湾), 01/11/2021 20:17:11
1F：推 jason35512: 我的理解是第一题是undirected graph 01/12 14:35
2F：→ jason35512: 是可以用mst algorithm算出来而且答案同dijkstra 01/12 14:35
3F：→ jason35512: 但第二题是directed graph就不能了 只能用dijkstra 01/12 14:35
5F：→ jason35512: m 01/12 14:36
6F：推 nofucknolove: mst只能保证整棵树最小，但不能保证va->vb最小。 01/20 11:33
7F：→ nofucknolove: 所以不能用mst吧 01/20 11:33