有关图的最小花费的算法题

该题的描述是这样的:

已知一幅有n个点和m条边组成的无向无环图,每个点和每条边都有一个数值。

我们可以在每个点上建立一个光源,耗费为其对应的数值,可以在每条边上建立一条光路,耗费也为其对应数值。

接下来我们定义一个点为bright当且仅当:

1.有一个光源建立在这个点上,或者;

2.有一条光路连接了这个点和一个bright的点。

我们想要求使整张图的点bright的最小花费。

望采纳!!点击回答右侧采纳即可采纳!!!这道题可以使用最小生成树算法来解决。

首先对于图中的每个点,考虑是否建立光源。如果建立光源,那么这个点就是bright的,否则就不是bright的。

然后考虑图中的边。对于每条边,计算出连接两个端点的最小花费。如果这两个端点中至少有一个是bright的,那么就建立光路,否则不建立。

最后将图中所有的边按照花费从小到大排序,依次加入最小生成树中,直到整张图中所有的点都是bright的。

这样就可以得到使整张图的点bright的最小花费了。