MST 挑战给出 "time exceeded" 错误

Question

我正在做 BLINNET problem on Sphere Online Judge，我需要找到最小生成树的成本。我应该遵循包含 Edge 和 Vertex 实例的结构。在这种情况下，顶点代表城市。

我收到 "time exceeded" 错误，我觉得 for 循环迭代太多是原因，但这是我能做的最好的。我想尝试二进制排序，看看它是否适用，但这并不容易，因为它应该使用 City class 中的 key 属性进行排序。

示例输入

2

4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1

3
ixowo
2
2 1
3 3
iyekowo
2
1 1
3 7
zetowo
2
1 3
2 7

示例输出

3
4

我的代码

import sys
import heapq

class City:

    def __init__(self, city_id):
        self.city_id = city_id
        self.key = float('inf')
        self.parent = None
        self.edge_list = list()
        self.visited = False
        #self.city_name = None

    def is_not_visited(self):
        if self.visited is False:
            return True
        return False

    def add_neighbor(self, edge):
        self.edge_list.append(edge)

    def __lt__(self, other):
        return self.key < other.key

class Edge:

    def __init__(self, to_vertex, cost):
        self.to_vertex = to_vertex
        self.cost = cost

#
# def find_and_pop(queue):
#     min = queue[0]
#     index = 0
#     for a in range(0, len(queue)):
#         if queue[a].key < min.key:
#             min = queue[a]
#             index = a
#     return queue.pop(index)
#

def MST(vertices_list):
    queue = vertices_list
    current = queue[0]
    current.key = 0
    #visited_list = list()
    #heapq.heapify(queue)
    total_weight = 0
    while queue:
        #current = find_and_pop(queue)
        current = queue.pop(0)
        for edge in current.edge_list:
            if edge.to_vertex.is_not_visited():
                if edge.cost < edge.to_vertex.key:
                    edge.to_vertex.key = edge.cost
                    edge.to_vertex.parent = current
        total_weight = total_weight + current.key
        current.visited = True
        queue = sorted(queue, key=lambda x: x.city_id)
        #heapq.heapify(queue)
        #visited_list.append(current)

    # total_weight = 0
    # for x in visited_list:
    #     total_weight = total_weight + x.key
    sys.stdout.write("{0}\n".format(total_weight))

class TestCase:
    def __init__(self, vertices):
        self.vertices = vertices

testcases = []

def main():

    case_num = int(sys.stdin.readline())
    #skip_line = sys.stdin.readline()
    for n_case in range(0, case_num):
        sys.stdin.readline()
        vertices_list = list()
        number_of_city = int(sys.stdin.readline())
        #interate and make for the time of number of cities
        for n_city in range(0, number_of_city):
            city = City(n_city)
            vertices_list.append(city)

        for n_city in range(0, number_of_city):
            c_name = sys.stdin.readline()
            #vertices_list[n_city].city_name = c_name
            num_neighbor = int(sys.stdin.readline())
            for n_neigh in range(0, num_neighbor):
                to_city_cost = sys.stdin.readline()
                to_city_cost = to_city_cost.split(" ")
                to_city = int(to_city_cost[0])
                cost = int(to_city_cost[1])
                edge = Edge(vertices_list[to_city-1], cost)
                vertices_list[n_city].edge_list.append(edge)

        testcase = TestCase(vertices_list)
        testcases.append(testcase)

    count = 0
    for testcase in testcases:
        MST(testcase.vertices)
        # if count < case_num -1:
        #     print()
        # count = count + 1



if __name__ == "__main__":
    main()

Answer 1

MST 循环中的 sorted 调用使解决方案效率低下。您有一些依赖于 heapq 的注释掉的代码，这确实是避免每次更改队列时都必须对其进行排序的方法。无论如何，我不明白你为什么要按城市 ID 对队列进行排序。如果有的话，它应该按 key.

排序

虽然它可以像你那样与 key 属性一起工作，但对我来说添加 edges 到队列（堆) 而不是顶点，因此您将边成本作为堆属性的基础。此外，该队列不应该从一开始就拥有所有项目，而是在算法期间选择它们时添加它们。并且，这更多地对应于 MST 构建算法，该算法逐条添加边，每次都具有最小成本。

如果边缘被推到堆上，它们必须是可比较的。因此 __lt__ 必须在边 class 上实现，就像您在顶点 class 上所做的那样。

class Edge:
    # ... your code remains unchanged... Just add:
    def __lt__(self, other):
        return self.cost < other.cost

def MST(vertices_list):
    # first edge in the queue is a virtual one with zero cost.
    queue = [Edge(vertices_list[0], 0)] # heap of edges, ordered by cost
    total_weight = 0
    while queue:
        mst_edge = heapq.heappop(queue) # pop both cost & vertex
        current = mst_edge.to_vertex
        if current.visited: continue
        for edge in current.edge_list:
            if not edge.to_vertex.visited:
                heapq.heappush(queue, edge)
        current.visited = True
        total_weight += mst_edge.cost

    sys.stdout.write("{0}\n".format(total_weight))

MST 挑战给出 "time exceeded" 错误

MST challenge gives "time exceeded" error

algorithm

priority-queue

minimum-spanning-tree

python-3.x

示例输入

示例输出

我的代码