[理工] 107台大资演 minimax path aa871220 PTT批踢踢实业坊

[理工] 107台大资演 minimax path

楼主: aa871220 (TMVP_Yueko) 2021-01-11 20:13:29

https://imgur.com/T8kbefI
我可以理解由dijkstra修改relax function 能得到这题的结果
正确性也想得出来
但是一开始解题想到的是用同样模板的Prim's algo以求MST
目前想不到怎么推翻之前的想法= =
想请教一下有没有反例会使得Prim是错误的

作者: jason35512 (jason2714) 2021-01-12 14:35:00

我的理解是第一题是undirected graph是可以用mst algorithm算出来而且答案同dijkstra但第二题是directed graph就不能了只能用dijkstrahttps://en.m.wikipedia.org/wiki/Widest_path_problem

继续阅读

[理工] 108中兴数学bobo1004 [理工] 108中兴资讯概论sososlee 109中兴资工数学和算法lucy35 [理工] 109中央算法seafoodccu [理工] 计系成大 106 (2)try66889 [理工] 台大电机丙离散ThereisBear 109中兴通讯 AM讯号IceHsuan [理工] 资演交大108 (10)(13)try66889 [理工] 106台联大计组drosyo [理工] 93 中山电机计组smalldata

Contact Us: admin [ a t ] ucptt.com