点击查看代码
print("学号：2023310143028")
点击查看代码
def prim(graph, start): num_nodes = len(graph) visited = [False] * num_nodes min_heap = [(0, start, -1)] mst_cost = 0 mst_edges = [] while min_heap: weight, u, parent = heapq.heappop(min_heap) if visited[u]: continue visited[u] = True mst_cost += weight if parent != -1: mst_edges.append((parent, u, weight)) for v in range(num_nodes): if not visited[v] and graph[u][v] != 0: heapq.heappush(min_heap, (graph[u][v], v, u)) return mst_cost, mst_edges graph = [ [0,20,0,0,15,0], [20,0,20,60,25,0], [0,20,0,30,18,0], [0,60,30,0,35,10], [0,0,0,10,15,0]
] mst_cost, mst_edges = prim(graph, 0)
print("Prim's MST Cost:", mst_cost)
print("Prim's MST Edges:", mst_edges)print("学号：3028")print("学号：2023310143028")
点击查看代码
import heapq initial_costs = [2.5, 2.6, 2.8, 3.1]
salvage_values = [2.0, 1.6, 1.3, 1.1]
maintenance_costs = [0.3, 0.8, 1.5, 2.0] dp = [[float('inf')] * 2 for _ in range(4)]
dp[0][1] = initial_costs[0] + maintenance_costs[0] for i in range(1, 4): dp[i][1] = min(dp[i-1][1] + maintenance_costs[i], initial_costs[i] + maintenance_costs[i]) if i > 0: dp[i][0] = dp[i-1][1] + salvage_values[i-1] min_cost = min(dp[3][1], min(dp[i][0] for i in range(3))) print(f"最优更新策略下的4年内最小总费用为：{min_cost}万元") print("学号：3028")print("学号：2023310143028")
