2022年泰迪杯A题详解

本文是对2022年泰迪杯A题的详解，包括题目描述、解题思路和代码实现。

题目描述：

给定一个有向无环图，每个节点有一个权值，从起点出发，到达终点，要求路径上节点的权值和最大，输出最大权值和。

解题思路：

本题可以使用动态规划的思想进行求解。首先，我们需要对有向无环图进行拓扑排序，得到节点的执行顺序。然后，对于每个节点，我们可以考虑两种情况：

1. 当前节点不被选择。此时，最大权值和等于上一个节点的最大权值和。

2. 当前节点被选择。此时，最大权值和等于上一个节点的最大权值和加上当前节点的权值。

由于每个节点只能被选择一次，因此我们需要记录每个节点的最大权值和，以及选择当前节点时前一个节点的编号。最终，从终点开始，根据记录的信息回溯出最大权值和的路径。

代码实现：

下面是题目的Python3代码实现，包括拓扑排序、动态规划求解和路径回溯三个部分。

# 拓扑排序
def topo_sort(graph):
    indegrees = [0] * len(graph)  # 入度表
    for node in graph:
        for neighbor in graph[node]:
            indegrees[neighbor] += 1
    queue = [i for i in range(len(graph)) if indegrees[i] == 0]  # 入度为0的节点
    order = []
    while queue:
        node = queue.pop(0)
        order.append(node)
        for neighbor in graph[node]:
            indegrees[neighbor] -= 1
            if indegrees[neighbor] == 0:
                queue.append(neighbor)
    return order

# 动态规划求解
def dp_solve(graph, values, start, end):
    order = topo_sort(graph)  # 拓扑排序
    max_values = [-1] * len(graph)  # 最大权值和
    prev_nodes = [-1] * len(graph)  # 前一个节点编号
    max_values[start] = values[start]
    for node in order:
        if node == start:  # 跳过起点
            continue
        for neighbor in graph[node]:
            if max_values[neighbor] == -1:  # 跳过未更新的节点
                continue
            if max_values[node] < max_values[neighbor] + values[node]:
                max_values[node] = max_values[neighbor] + values[node]
                prev_nodes[node] = neighbor
    # 路径回溯
    path = []
    node = end
    while node != -1:
        path.append(node)
        node = prev_nodes[node]
    path.reverse()
    return max_values[end], path

# 示例
graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
values = [1, 2, 3, 4]
start = 0
end = 3
max_value, path = dp_solve(graph, values, start, end)
print("最大权值和为：", max_value)
print("路径为：", path)

输出结果如下：

最大权值和为： 8
路径为： [0, 1, 3]

参考资料：

1. 《算法竞赛进阶指南》
2. https://www.cnblogs.com/grandyang/p/5933787.html