【用deepseek和chatgpt做算法竞赛】——还得DeepSeek来 -Minimum Cost Trees

【用deepseek和chatgpt做算法竞赛】——还得DeepSeek来 -Minimum Cost Trees_5

往期

【用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 defaultdict

def 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, graph

def process_and_output(file_path):
    graph_data = read_graph_from_file(file_path)
    if not graph_data:
        return


if __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 defaultdict


def 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, graph


def dijkstra(graph, start, delay_constraint):
    """ 使用 Dijkstra 算法找到从 start 到所有节点的最短路径 """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    path = {}

    while heap:
        current_distance, current_node = heapq.heappop(heap)

        if current_distance > delay_constraint:
            continue

        for neighbor, cost, delay in graph[current_node]:
            distance = current_distance + delay
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
                path[neighbor] = current_node

    return path


def build_tree(path, terminals):
    """ 根据路径构建树 """
    tree_edges = set()
    for terminal in terminals:
        current = terminal
        while current in path:
            parent = path[current]
            tree_edges.add((parent, current))
            current = parent
    return tree_edges


def 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] = 0
        heap = [(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 + delay
                    if distance < distances[neighbor]:
                        distances[neighbor] = distance
                        heapq.heappush(heap, (distance, neighbor))

        for terminal in terminals:
            if distances[terminal] > D:
                return False
        return True

    delay_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()