[理工] 算法187（106台大）！ Aa841018 PTT批踢踢实业坊

[理工] 算法187（106台大）！

楼主: Aa841018 (andrew) 2019-07-04 08:56:26

https://i.imgur.com/AcOhtV8.jpg
https://i.imgur.com/0vaD1Hl.jpg
https://i.imgur.com/yJuU2Kl.jpg
想请教一下，为何将G的点、边看过就可得出是optimal?
证optimal不是应该利用矛盾证法确定找不出更小的MST才是吗？

作者: mathtsai (mathtsai) 2019-07-04 13:04:00

这题和MST有啥关系？题目一开始不就说是有向无环图了？MST的定义是给定一个graph找到让所有点"互通" 并且使cost最小"有向图" 不会 "互通"，你对于定义好像没弄得很清楚这题要找以capital为source的SSSP才对SSSP每次找出值最小的node去更新其他node的值所以保证每个node都会是最小的 (optimal)不晓得这样有没有解释到你的问题？

楼主: Aa841018 (andrew) 2019-07-04 13:42:00

谢谢解释，我懂了！

继续阅读

线代 4-126 范例三houallan5478 [理工] 线代内积空间shinle14 [理工] 资料结构p35第5题david95525 [理工] 线代8-59_范例3fmtshk Re: 线代3-30Honor1984 线代3-30zxc2179vbnm 离散递回排组Yueh711 离散关于循环群AdonisLam 线代证明RS（AB)=RS(B)是要加什么条件zxc2179vbnm Re: [理工] 资料结构 circular Queue问题kyuudonut