Browse Category

最小生成树

蓝桥杯 城市建设 (Kruskal)

栋栋居住在一个繁华的 C 市中,然而,这个城市的道路大都年久失修。市长准备重新修一些路以方便市民,于是找到了栋栋,希望栋栋能帮助他。
C 市中有 n 个比较重要的地点,市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点,每条道路可以连接其中的两个地点。另外由于 C 市有一条河从中穿过,也可以在其中的一些地点建设码头,所有建了码头的地点可以通过河道连接。
栋栋拿到了允许建设的道路的信息,包括每条可以建设的道路的花费,以及哪些地点可以建设码头和建设码头的花费。
市长希望栋栋给出一个方案,使得任意两个地点能只通过新修的路或者河道互达,同时花费尽量小。

POJ 1789 Truck History (最小生成树)

用一个7位的string代表一个编号,两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号衍生出来,代价是这两个编号之间相应的distance,现在要找出一个衍生方案,使得所有的编号之间都可以直接或者间接形成转换,并且总代价最小,也就是distance之和最小。

POJ 3026 Borg Maze (最小生成树)

从 S 出发,去到达每一个 A ,求最小的总路径长度,空格是空地,# 是墙,并且在走的过程中我们可以在 S 或 A 点分裂,也就是从该点可以延伸出多条路径到其他点,但是每一次只能让其中的一个继续行走。