[理工] 104交大资演！（MST) Aa841018 PTT批踢踢实业坊

[理工] 104交大资演！（MST)

楼主: Aa841018 (andrew) 2019-12-23 09:57:04

https://i.imgur.com/Jtt4Axj.jpg
请问（b)(c)，（c)我可以理解，但为什么（b)多了个if就错了？
然后，详解我看不是很懂…

作者: gash55025502 (白影弓) 2019-12-23 11:42:00

他们的if P then Q的P跟Q是反过来的b可以简单举个反例如三点两边权重都1 此时MST唯一但light edge不唯一c则可以用Prims algorithm去想在prims回合每个回合都是挑当下cut权重最小的边那既然题目说每个cut此种边都唯一当然造出来的MST也会唯一

作者: AirComm (AirComm) 2019-12-23 16:47:00

有人可以翻译一下b选项吗？light edge 是啥

作者: mistel (Mistel) 2019-12-23 16:49:00

就是横跨两个切集权重最小的那个边

楼主: Aa841018 (andrew) 2019-12-23 21:47:00

哦！谢谢各位！

继续阅读

[理工] 104台大资工 x86 string问题gash55025502 [理工] 97清大资工计组harryju3 [理工] 资演 105交大（19）（21）ching4562 [理工] 离散_机率fmtshk [理工] 105 交大资演数题 3 9 10 19dsa66253 [理工] 计组管线lucy35 [理工] 成大计组eric17195 [理工] 106北大数学sung100kg [理工] OS process synchronizationAdonisLam [理工] 105交大（BFS)!Aa841018

Contact Us: admin [ a t ] ucptt.com