网站被k什么意思,体育直播网站建设,怎么查询网站所有关键词,杭州装饰网站建设往期
【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_0#xff1a;介绍了题目和背景【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_1#xff1a;题目输入的格式说明#xff0c;选择了邻接表…往期
【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_0介绍了题目和背景【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_1题目输入的格式说明选择了邻接表来表示图【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_2介绍了邻接表题目输出的格式说明【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_3期主要写一个初代程序能完整一些简单的例子【用deepseek和chatgpt做算法竞赛】——ChatGPT还是不行呀 -Minimum Cost Trees_4介绍了评分规则让GPT输出了一个看着正确实际不行的代码
这一期我选择用伪代码的方式与GPT沟通让GPT做军师和程序员一定要写一个有分的程序呀
0 基础程序
下面这个程序就是根据题目要求写的一个输入数据读取的程序
import sys
import heapq
from collections import defaultdictdef read_graph_from_file(file_path): 从文件读取图数据并解析 with open(file_path, r) as f:lines f.read().strip().split(\n)n int(lines[0].strip()) # 节点数s int(lines[1].strip()) # 源点k int(lines[2].strip()) # 目标节点数terminals list(map(int, lines[3].strip().split())) # 目标节点列表D int(lines[4].strip()) # 延迟约束m int(lines[5].strip()) # 边数graph defaultdict(list)for i in range(6, 6 m):a, b, c, d map(int, lines[i].strip().split())graph[a].append((b, c, d)) # 存储 a - b 的边graph[b].append((a, c, d)) # 存储 b - a 的边无向图return n, s, terminals, D, graphdef process_and_output(file_path):graph_data read_graph_from_file(file_path)if not graph_data:returnif __name__ __main__:# 输入文件路径file_path ../sample-cases/01 # 请根据实际文件路径修改process_and_output(file_path)1 ChatGPT思路
ChatGPT给的思路流程
初始化图数据构建主树构建冗余树验证冗余树输出 这个其实就有问题了因为先构建出主树为了找到一颗最好的主树就很有可能把冗余树堵死了
2 从简单的开始
我们先尝试只找一棵树即只要拿前两个条件的分
单棵树: 如果是单棵树得 5 分。满足延迟约束的单棵树: 如果树满足延迟约束则得 10 分。 很尴尬的事情发生了ChatGPT崩了接下的事情让deepseek来吧我用的是浙江大学的满血版DeepSeek的“浙大先生” 实际使用还是有一些问题就是输入框很小呀一次只能能看到一行呀看不到我完整的输入修改起来比较麻烦但是是免费的就很棒现在是2025年2月21日希望后面能改进感谢浙大
deepseek给出的代码如下
满足了简单的要求能找到一颗树了且拿到了分
import sys
import heapq
from collections import defaultdictdef read_graph_from_file(): 从标准输入读取图数据并解析 lines sys.stdin.read().strip().split(\n)n int(lines[0].strip()) # 节点数s int(lines[1].strip()) # 源点k int(lines[2].strip()) # 目标节点数terminals list(map(int, lines[3].strip().split())) # 目标节点列表D int(lines[4].strip()) # 延迟约束m int(lines[5].strip()) # 边数graph defaultdict(list)for i in range(6, 6 m):a, b, c, d map(int, lines[i].strip().split())graph[a].append((b, c, d)) # 存储 a - b 的边graph[b].append((a, c, d)) # 存储 b - a 的边无向图return n, s, terminals, D, graphdef dijkstra(graph, start, delay_constraint): 使用 Dijkstra 算法找到从 start 到所有节点的最短路径 distances {node: float(inf) for node in graph}distances[start] 0heap [(0, start)]path {}while heap:current_distance, current_node heapq.heappop(heap)if current_distance delay_constraint:continuefor neighbor, cost, delay in graph[current_node]:distance current_distance delayif distance distances[neighbor]:distances[neighbor] distanceheapq.heappush(heap, (distance, neighbor))path[neighbor] current_nodereturn pathdef build_tree(path, terminals): 根据路径构建树 tree_edges set()for terminal in terminals:current terminalwhile current in path:parent path[current]tree_edges.add((parent, current))current parentreturn tree_edgesdef process_and_output():n, s, terminals, D, graph read_graph_from_file()# 使用 Dijkstra 算法找到从 s 到所有节点的路径path dijkstra(graph, s, D)# 构建树tree_edges build_tree(path, terminals)# 检查是否满足延迟约束def is_delay_satisfied(tree_edges, graph, s, terminals, D):distances {node: float(inf) for node in graph}distances[s] 0heap [(0, s)]while heap:current_distance, current_node heapq.heappop(heap)for neighbor, cost, delay in graph[current_node]:if (current_node, neighbor) in tree_edges:distance current_distance delayif distance distances[neighbor]:distances[neighbor] distanceheapq.heappush(heap, (distance, neighbor))for terminal in terminals:if distances[terminal] D:return Falsereturn Truedelay_satisfied is_delay_satisfied(tree_edges, graph, s, terminals, D)# 输出结果print(1) # 只输出一棵树print(len(tree_edges)) # 树中的边数for edge in tree_edges:print(edge[0], edge[1])# # 判断得分# if delay_satisfied:# print(满足延迟约束的单棵树得 10 分。)# else:# print(单棵树得 5 分。)if __name__ __main__:process_and_output()恭喜恭喜有分了虽然垫底但迈出了第一步祝贺
目前得分是452893下一期争取拿更高
