作者ooww (选ばれし子どもたち)
看板Math
标题[其他] 最小成本扩张树(Kruskal)
时间Sun May 23 14:57:35 2021
如图所示
https://imgur.com/a/stiLyaS
请问第二小题
右边参考公职王解答，
看不太懂红色底线的意思，
中间图树我依照解答画出
第6、7点，分支0-3将含4段连线...这段话看不太懂
希望神人解释
或是可能解答有误，
跪求神人解惑
我知道Kruskal是依序加入最小边，但不能有回圈
可是第二小题条件看不是很懂
愿奉上300P感谢帮忙
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.121.236.146 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1621753058.A.122.html
1F：推 RicciCurvatu: 0分出去的任何一条都叫分支 一个分支最多三条线 05/23 15:01
跪求大大可以画图帮助我理解
还是听不太懂
※ 编辑: ooww (122.121.230.234 台湾), 05/23/2021 16:55:01
2F：推 RicciCurvatu: 0-3-2-1 是一个分支 05/23 17:00
3F：→ RicciCurvatu: 0-4-5-6是一个分支 05/23 17:00
4F：推 LPH66 : 在到 20 那条边时, 如果加进去则从 0 出发往 3 这边 05/24 05:48
5F：→ LPH66 : 将有 0-3 3-2 2-1 2-6 四个连线, 不合条件 05/24 05:48
感谢解惑
另外请教您，
题目说起始节点0，
若起始节点改为2或3或4，
结果是否一样没变?
※ 编辑: ooww (218.166.99.191 台湾), 05/25/2021 02:20:29