Browse Category

最小生成树

POJ 1789 Truck History (最小生成树)

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

POJ 3026 Borg Maze (最小生成树)

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