加权桥梁连通：玩法与打印材料

选择总成本较低的边连接全部地点，允许分支。

人数

1–6人（合作）

时间

15–20分钟

材料

五节点图、边成本清单与连通记录

只用清单桥

地点A至E，可选无向桥AB成本2、AC4、BC1、BD5、CD3、CE6、DE2。任一方向可走，每桥只付一次，其他地点对没有桥。成本是虚构计子，不是真实路长或施工报价，初始五地分离。

全网连通

选桥使任意两地都能通过选中桥互达，允许分支，不要求一条路线各点恰过一次。E孤立则无效，即使A至D很便宜。逐条画线、每成本加一次，重复买AB不能增加连通。

核对方案

AB、BC、CD、DE总2+1+3+2=8，从E可到D、C、B、A。AC、BC、CD、DE也全连通但值10。AB、BC、DE仅值5却分两组，不是解。先验连通再比价格。

说明最优

五个分离地点至少需要四条连接边。一种方法按成本从小到大考虑，仅当一边连接两个原先不同组才加入，直至成一组。本图BC、AB、DE、CD得到8，为给定正成本无向图的最小生成树，不是只求A到E最短路。

分工与结束

可轮流提议边、查成本或追踪连通，不限时。未采用建议另记，不把所有画线都当已购买。可代描路径、读清单。全员能解释连通方案及最佳总值后对照独立答案页。纸图无自动检测或网络动画。

打印材料

先看预览，100%比例打印，关闭浏览器页眉页脚。剪裁请使用合适工具，主持答案页另收好。本页为手动桌面材料，无在线对手、自动裁判或求解器。