从源节点开始查找具有最大权重或增益的给定长度的路径

Question

您好，感谢您阅读本文。

给定一个包含 N 个顶点和 e 条边的无向树以及关联的奖励点 P_e，起始顶点：s 和一个整数：M

然后我们必须找到：从 s 开始，遍历 M 条边，我们可以获得的最大点数。

一条边可以遍历多次

请指导我正确的方向来解决这个问题。

Answer 1

首先我们观察一下，如果你在最优解中多次遍历某条边，那么所有这些边都会有相同的奖励（否则越多遍历奖励越大的边越有利）。因此，在不失慷慨的情况下，我们可以说您将多次遍历一条边。

其次，您将多次遍历的边将是您最佳路径中所有边中奖励最大的边。否则，再次遍历奖励更大的路径会更有利可图，而路径将不是最优的。因此，您将多次遍历的边缘将是您路径中的最后一个边缘。

所以这里有一个简单的算法：遍历树中所有距离起点不超过M的顶点，求出从s到每个没有边重复的顶点的奖励点数之和（这个number 将以唯一的方式确定，因为树中每对顶点之间只有一条路径），并使用其余 M 条边遍历奖励最大的边（每次我们都认为这条边是最后一条）我们在当前路径中使用的一个）。

您可以使用BFS or DFS

这是一个伪代码：

ans = -INF

traverse(vertex, pathLength, pathReward, lastEdge) {
    if (visited(vertex)) // Do not visit a vertex twice
        return;
    if (pathLength > 0)
        ans = max(ans, pathReward + (M - pathLength) * lastEdge)
    if (pathLength == M) // We cannot go farther than M edges
        return;
    for (vertex, nextVertex) in edges:
        edgeReward = edgeReward(vertex, nextVertex)
        traverse(nextVertex, pathLength + 1, pathReward + edgeReward, edgeReward)
}

你会打电话 traverse(0, 0, 0, -INF) 然后从 ans.

得到结果

从源节点开始查找具有最大权重或增益的给定长度的路径

Find path of given length with max weight or gain starting from source node

algorithm

tree

graph