BOK-1197最小生成ツリー

ソース:https://www.acmicpc.net/problem/1197

質問する

グラフィックが与えられると、そのグラフィックの最小生成ツリーを求めるプログラムが作成されます.
最小生成ツリーは、指定されたシェイプのすべての頂点を接続する一部のシェイプの重み付けと最小のツリーです.

入力

第1行は、頂点の個数V(1≦V≦10000)および幹線の個数E(1≦E≦100000)を与える.次のE行は、各幹線の情報を表す3つの整数A、B、Cを与える.これは、A番頂点とB番頂点が重み付けCの幹線接続であることを意味する.Cは負数の可能性があり、節価は1000000を超えない.
グラフィックの頂点は1番からV番までで、どちらの頂点にもパスがあります.最小生成ツリーの重みは-24748648以上であり、2147483647以下のデータのみが入力されます.

しゅつりょく

最初の行に最小生成ツリーの重み値を出力します.

例

👉 入力-指定されたテストケース

3 3
1 2 1
2 3 2
1 3 3

🔥 ex2 input)

5 7
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
4 5 2

👉 しゅつりょく

3

🔥 ex2 output)

5

解答方法

最小生成木を求める問題としてKruskalまたはPrimを用いて近似解を行うことができる.

Kruskal Algorithm

注-Kruskalアルゴリズム位置決め

💡 実施が必要な内容

find機能:

タスク検索するノードの最上位の親ノード

union機能:親が違う場合は、より小さな親で各親の仕事を統一する

edgeナビゲーション:

、ナビゲーション中に整列が選択されたかどうかを判断するためのedge(幹線)

""" Kruskal """
import sys

V, E = map(int, sys.stdin.readline().strip().split())
edges = []
for _ in range(E):
    src, dest, w = map(int, input().split())
    edges.append((w, src, dest))


def find(parent, node):
    if parent[node] == node: return node
    else: return find(parent, parent[node])


def union(parent, v1, v2):
    if v1 > v2: parent[v1] = v2
    else: parent[v2] = v1


def solution(V, E, edges):
    # sort by weights
    edges.sort(key=lambda x: x[0])
    parent = [e for e in range(V + 1)]

    answer, cnt = 0, 0
    for edge in edges:
        pv1 = find(parent, edge[1])
        pv2 = find(parent, edge[2])
        
        if pv1 != pv2:
            cnt += 1
            union(parent, pv1, pv2)
            answer += edge[0]
            if cnt == V - 1: break
    return answer

print(solution(V, E, edges))

Prim Algorithm

💡 実施が必要な内容

図、頂点と幹線を示す

図

データ構造

は、bfsなどのアクセスしたノードを表示するために使用される

minheapからなる生成ツリー

""" Prim """
from heapq import heappush, heappop

V, E = map(int, input().split())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
    src, dst, w = map(int, input().split())
    graph[src].append((dst, w))
    graph[dst].append((src, w))

answer = 0
visited = [False for _ in range(V + 1)]
q = [(0, 1)]  # w, node
cnt = 0

while cnt < V:  # cnt == V - 1 -> break
    w, node = heappop(q)

    if visited[node] == False:
        visited[node] = True
        answer += w
        cnt += 1
        for nv, nw in graph[node]:
            heappush(q, (nw, nv))

Kruskalの時間的複雑度が幹線の個数eである場合、それはO(elog 2 e)O(elog 2 e)O(elog 2 e)O(elog 2 e)でなければならず、Primの時間的複雑度はグラフィック頂点の個数nであり、それはO(n 2)O(n^2)O(n^2)O(n 2)O(n 2)O(n 2)でなければならない.

学習の過程で書かれたコードは,解答者のコードを見て修正されたが,論理的にはほぼ同じ過程が実現し,時間差が大きい.😭
上のコードは5028 msがKruskal,5336 msがPrimアルゴリズムを用いたコードであり,速度的には不明である.
484 msの正解のコードをもう一度分析します.🧐

import sys

def find(x):
    global parent
    if parent[x] == x: return x
    else: return find(parent[x])

def union(x, y):
    pX, pY = find(x), find(y)
    if pX > pY: parent[pX] = pY
    else: parent[pY] = pX

V, E = map(int, sys.stdin.readline().strip().split())
arr, parent = [], [i for i in range(V + 1)]
for _ in range(E):
    v1, v2, w = map(int, sys.stdin.readline().strip().split())
    arr.append([w, v1, v2])
arr.sort()
result = 0
for a in arr:
    if find(a[1]) == find(a[2]): continue
    union(a[1], a[2])
    result += a[0]
print(result)