[これがコードテスト]図論-都市分割計画

グラフィックアルゴリズム
1.集合する

union:2つの要素を含む集合を1つの集合に結合する演算

find:ある要素が属する集合が何であるかを示す演算

2.神装樹

1つのグラフィックを含む場合、すべてのノードを含み、ループが存在しないローカルグラフィック

クルーズアルゴリズム(最小拡張ツリーアルゴリズム、階調)

3.位相整列アルゴリズム

方向図のすべてのノードを順番にリストし、方向性に反することを避ける

白峻1647号です.
🔗 質問リンク
https://www.acmicpc.net/problem/1647
問題の説明

import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())

parent = [0] * (N + 1)

for i in range(1, N + 1):
    parent[i] = i

edges = []
result = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append((C, A, B))

edges.sort()
# 유지 비용이 가장 큰 경로 없애서 마을 분리 
last = 0

for edge in edges:
    C, A, B = edge
    if find_parent(parent, A) != find_parent(parent, B):
        union_parent(parent, A, B)
        result += C
        last = C

print(result - last)

まず,最小伸長木をクルーズアルゴリズムにより確立した.2つの村を分け、維持費を最小限に抑えるため、村の道路の中で維持費が最も高い道路を廃止した.メンテナンス費用の和を示す結果からソート費用の最後の値を減算し、上記条件を満たす最小メンテナンス費用の和を求める.
📝 整理する
接続ノードの幹線を最小限に抑え、周期を持たないには、クルーズアルゴリズムを使用する必要があります.
入力値が多すぎてクイズがタイムアウトした場合は、import sys / input = sys.std.readlineを使用します.