[python]1922号:ネットワーク接続

ネットワーク接続:https://www.acmicpc.net/problem/1922


この問題を解決する前に、最小生成ツリーについて説明します.
これは、ノード全体を最小限のコストで迂回できる問題であり、多くの問題が通信ネットワークの構築に関連している.
また,最小伸長木は周期を含まず,最小コストの幹線からなる.

クルーズアルゴリズム

私はクルーズアルゴリズムを用いた.これはgreedyアルゴリズムを用いてネットワーク内のすべての頂点を最小コストで解く方法である.
解決ロジックは次のとおりです.
1.グラフ内の幹線を昇順に並べます.
2.周期が発生しない幹線を選択します.
3.最小費用伸長ツリーのセットに幹線を追加します.
例を挙げて説明する.
1と3を結ぶ幹線は5の料金がかかります.
2と3を結ぶ幹線は10代かかります.
1と2を結ぶ幹線は4の料金がかかります.

では、このようにこれらの幹線を解いて位置合わせします.

次に、ループを作成しない幹線を選択します.
最小値1と2を接続します.

次に、小さい値1と3を接続します.

最後のノードしか残っていませんが、そのノードを接続した瞬間にループするので接続しません.

では、サイクルがあるかどうかをどのようにチェックしますか?
ここにUnion-Findの概念が現れ、
各ノードの祖先(親)ノードを検索し、祖先ノードが異なる場合は接続します.
そして接続(union)するたびに料金計算が終わります!

from gettext import find
import sys
from collections import deque
from unittest import result
input = sys.stdin.readline

# 컴퓨터의 수
N = int(input())
# 선의 수
M = int(input())

parent = [i for i in range(N+1)]
edges = []
for _ in range(M):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

# 최소길이로 정렬해 놓음
edges.sort()

# 부모 노드를 찾아야함 -> 사이클을 만들지 않기 위해서
# 부모 노드를 찾기 위해서는 union-find를 사용한다.
# 재귀함수를 통해 가장 작은 값을 가리키는 것을 찾아줌
# ex) 1-2-3이 연결되어 있으면 table은 1 1 2 가 될 것임, 3은 2와 연결되어있고 재귀함수를 통해 2의 연결 값인 1을 연결해준다.
def get_parent(parent, x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent, parent[x])
    return parent[x]


# 사이클이 없으면 합쳐준다
def union(parent, a, b):
    a = get_parent(parent, a)
    b = get_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b    


def kruskal(edges):
    result = 0
    for edge in edges:
        cost, a, b = edge

        if get_parent(parent, a) != get_parent(parent, b):
            union(parent, a, b)
            result += cost
    return result
result = kruskal(edges)
print(result)

この問題は1197問題の入力部分と同じです.
次のPostingでは、現在の概念でより深化している問題「需要電力(https://www.acmicpc.net/problem/10423)」を解く.