[問題解決]Back-1197最佳源生成ツリー(図)

提问链接

問題の説明

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

入力

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

しゅつりょく

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

入力例1

3 3
1 2 1
2 3 2
1 3 3

サンプル出力1

3

私の答え

これはクルースカアルゴリズムを利用した問題である.

クルーズとグリディ

最小生成ツリー(MST)を実現するアルゴリズム.
クルースカは非周期的最小コスト幹線を選択する方法である.
これは그리디タイプで、すべての頂点を最小費用に接続する最適な値を求めます.
グリディはその瞬間に最善の選択をするので、全体的に最善の選択ではないかもしれません.
逆に、クルーズはMSTを利用して最適な答えを出した.

クルーズナイフアクション

加重昇順ソート

[位置合わせされた幹線](Aligned Wire)リストからループを作成しない幹線を選択

最低重み優先選択

周期を形成する幹線を除き、

.
3.現在のmst(最小コスト拡張ツリー)セットに幹線を追加

実施時の注意

次のオプションを選択してコレクションに追加するときにループを作成するかどうかを確認します.

を追加する新幹線の両端の頂点が同じセットにある場合、

サイクルが形成される.

ループを作成するかどうか

union-findアルゴリズム

union:2つのコレクションを1つのコレクションにマージする演算 find:ルートディレクトリにルーティングされた各ノードの親ノードをルートディレクトリに更新します。

を適用

パス圧縮は

と呼ぶ.

コード#コード#

v, e = map(int, input().split())
graph = []
for i in range(e):
    a, b, c = map(int, input().split())
    graph.append((a, b, c))
graph.sort(key = lambda x: x[2]) #가중치 오름차순 정렬

mst = [] # 최소신장 트리 담는 리스트
p = [0] # 상호배타적 집합

for i in range(1, v+1):
    p.append(i) # 각 정점 자신이 집합의 대표

def find(u): # 각 노드의 루트 정점 찾기
    if u != p[u]:
        p[u] = find(p[u]) # 경로 압축
    return p[u]

def union(u,v):
    root1 = find(u)
    root2 = find(v)
    p[root2] = root1 # 결합. 두변수가 바뀌어도 됨
    
edges = 0 # 간선 개수
cost = 0 # 가중치 합

while True:
    if edges == v-1: # 크루스칼은 정점-1개의 간선을 선택
        break
    u, w, t = graph.pop(0) # 오름차순이니까 가중치작은 것부터 pop
    if find(u) != find(w): #u와 v가 서로 다른 집합에 속해 있으면
        union(u, w)
        mst.append((u, w))
        cost += t 
        edges += 1
print(cost) # 최소신장트리 가중치 합
#  print(mst) # 최소신장트리