user24714692's questions

问题陈述

给定一个带权无向图 G，有 N 个顶点，编号为 1 到 N。最初，G 没有边。

您将执行 M 次操作来向 G 添加边。第 i 次操作 (1≤i≤M) 如下：

给定一个由 K _{i个顶点组成的顶点子集 S i} ={A _i,1 , A _i,2 , ,…,A _i,Ki } 。对于每对 u,v 使得 u,v ∈ S _i且 u<v，在顶点 u 和 v 之间添加一条权重为 C _{i 的}边。​ 执行完所有M个操作后，判断G是否连通。如果是，求 G 的最小生成树中边的总权重。

代码

from collections import defaultdict


def solution(A):
    class Kruskal:
        def __init__(self, G):
            self.G = G
            self.parent = {}
            self.rank = {}
            self.make_sets()

        def make_sets(self):
            for u, v in self.G:
                if u not in self.parent:
                    self.parent[u] = u
                    self.rank[u] = 0
                if v not in self.parent:
                    self.parent[v] = v
                    self.rank[v] = 0

        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, u, v):
            su, sv = self.find(u), self.find(v)
            if su != sv:
                if self.rank[su] > self.rank[sv]:
                    self.parent[sv] = su
                else:
                    self.parent[su] = sv
                    if self.rank[su] == self.rank[sv]:
                        self.rank[sv] += 1

        def _mst(self):
            mst = []
            for edge in self.G.keys():
                u, v = edge
                if self.find(u) != self.find(v):
                    self.union(u, v)
                    mst.append((u, v, self.G[edge]))
            return mst

    N, M = A[0]
    graph = defaultdict(int)
    for i in range(1, len(A)):
        if i % 2 == 1:
            k, c = A[i]
        else:
            edges = A[i]
            for ii in range(len(edges)):
                for jj in range(ii + 1, len(edges)):
                    if edges[ii] < edges[jj]:
                        if (edges[jj], edges[ii]) not in graph or (edges[ii], edges[jj]) not in graph:
                            graph[(edges[jj], edges[ii])] = c
                            graph[(edges[ii], edges[jj])] = c
                            continue
                        if (edges[jj], edges[ii]) in graph and graph[(edges[jj], edges[ii])] > c:
                            graph[(edges[jj], edges[ii])] = c
                        if (edges[ii], edges[jj]) in graph and graph[(edges[ii], edges[jj])] > c:
                            graph[(edges[ii], edges[jj])] = c

    kruskal = Kruskal(graph)
    MST = kruskal._mst()
    res = 0
    nodes = set()
    # print(MST)
    for x, y, z in sorted(MST, key=lambda o: o[-1]):
        res += z
        nodes.update({x, y})

    if sorted(nodes) != list(range(1, N + 1)):
        print(-1)
    else:
        print(res)


A = [[10, 5], [6, 158260522], [1, 3, 6, 8, 9, 10], [10, 877914575], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
     [4, 602436426], [2, 6, 7, 9], [6, 24979445], [2, 3, 4, 5, 8, 10], [4, 861648772], [2, 4, 8, 9]]

solution(A)

问题

它输出：4302960910. 预期输出是1202115217. 我错过了什么？

选择：

from collections import defaultdict
from heapq import heappush, heappop


def solution(A):
    def prim(G):
        vis = set()
        start, dest = next(iter(G))
        vis.add(start)
        Q, mst = [], []
        for (start, nei), w in G.items():
            heappush(Q, (w, start, nei))
        while Q:  # and len(vis) < len(G):
            # print(Q)
            w, src, dest = heappop(Q)
            if dest in vis:
                continue
            vis.add(dest)
            mst.append((src, dest, w))
            for w, nei in G[dest]:
                heappush(Q, (w, dest, nei))
        return mst

    N, M = A[0]
    graph = defaultdict(list)
    for i in range(1, len(A)):
        if i % 2 == 1:
            k, c = A[i]
        else:
            edges = A[i]
            for ii in range(len(edges)):
                for jj in range(ii + 1, len(edges)):
                    if edges[ii] < edges[jj]:
                        if (edges[jj], edges[ii]) not in graph:
                            graph[(edges[ii], edges[jj])] = c
                            graph[(edges[jj], edges[ii])] = c
                            continue

                        if (edges[jj], edges[ii]) in graph and graph[(edges[jj], edges[ii])] > c:
                            graph[(edges[jj], edges[ii])] = c
                        # if (edges[ii], edges[jj]) in graph and graph[(edges[ii], edges[jj])] > c:
                        #     graph[(edges[ii], edges[jj])] = c

    mst = prim(graph)
    res = 0
    s = set()
    for x, y, w in mst:
        res += w
        s.update({x, y})

    if sorted(s) != list(range(1, N + 1)):
        print(-1)
    else:
        print(res)


A = [[10, 5], [6, 158260522], [1, 3, 6, 8, 9, 10], [10, 877914575], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
     [4, 602436426], [2, 6, 7, 9], [6, 24979445], [2, 3, 4, 5, 8, 10], [4, 861648772], [2, 4, 8, 9]]
solution(A)

替代算法似乎“部分”起作用，但我仍然不确定它是否已正确实现？

伪代码

algorithm Kruskal(G) is
    F:= ∅
    for each v in G.V do
        MAKE-SET(v)
    for each {u, v} in G.E ordered by weight({u, v}), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F := F ∪ { {u, v} }
            UNION(FIND-SET(u), FIND-SET(v))
    return F

如何在线运行代码？

• 使用我的 Ideone 模板。
• solution用你正确的方法改变方法solution。
• 在此链接中提交您的代码（需要登录用户名和密码）。