Algorithm/これがコードテスト/図論/都市分割計画です

📖質問する
動物園から逃げ出したばかりのサルが世界を一周している.ある日、サルが平和村にしばらくいると、ちょうど村の人が道路工事のために会議をしていました.
村はN軒の家とそれらの家を結ぶM本の道で構成されている.道はどんな方向にも通行できる歩道です.そして、どの道にも維持費があります.
村の里長は何とかして村を二つの別々の村に分割しようとしている.村が大きすぎて、一人では管理できません.村を分割するときは、別々の村の家屋を互いにつながっている部分に分割します.これは、分離された村ごとに任意の2つの家の間に必ず道があることを意味します.村には1軒以上の家が必要だ.
こうして、村の里長は計画を立てているうちに、村の道が多すぎると思った.いったん離れた2つの村の間の道は必要なく、取り除くことができます.そして、それぞれの離れた村には、任意の2つの家の間の経路が常に存在し、道路をさらに解消することができる.村の里長は上記の条件を満たすために、すべての道を除いて、残りの道の維持費の和を最小限に抑えたいと思っています.これを求めるプログラムを書いてください.
📝解法

の1つの村を2つの分離した村に分割し,分離した村では任意の2つの家の間の無条件経路を満たしながら道路の個数を最小限に保つために「最小伸長木」アルゴリズムを用いるべきであると考えられる.

まず村を問わず、クルーズアルゴリズムを使用して最小伸長木を構築し、最小のメンテナンス費ですべての家を接続します.

の最小身長木を構成するとともに、維持費が最も高い道路を除けば2つの村に分けられ、問題に条件が与えられた(分離した村では、すべての家がつながっていなければならず、維持費が最も低くなければならない).田野は満足できる.

入力条件

の最初の行は家の個数Nを与えて、道の個数M.Nは2以上100000以下の整数、Mは1以上100000以下の整数である.

以降、M行から道路の情報はA、B、Cの3つの整数で空白に分けられ、A号家とB号家を結ぶ道路の維持費がC(1<=C<=1000)であることを示す.

しゅつりょくじょうけん

の最初の行では、道路がキャンセルされ、残りのメンテナンス費用の最高値が出力されます.

パスワード

# 리스트를 정렬하기 위한 퀵정렬 코드
def quick_sort(a, start, end):
  if end - start <= 0:
    return
  pivot = a[start]
  i = start + 1
  j = end
  while True:
    while a[i] < pivot and i <= end: i += 1
    while a[j] > pivot and j >= start : 
      j -= 1
    if i < j:
     a[i], a[j] = a[j], a[i]
    else:
      a[j], a[start] = a[start], a[j]
      break
  quick_sort(a, start, j - 1)
  quick_sort(a, j + 1, end)

# 특정 집이 속한 집합을 찾기
def find_parent(parent, a):
  if parent[a] != a:
    parent[a] = find_parent(parent, parent[a])
  return parent[a]

# 두 집이 속한 집합을 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a > b:
    parent[a] = b
  elif b > a:
    parent[b] = a
    
# n, m을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 자신의 부모 노드를 자신으로 초기화
parent = [0] * (n + 1)
for i in range(n + 1):
  parent[i] = i

# 모든 길 정보를 담을 리스트(유지비, 집1, 집2)
roads = []
for _ in range(m):
  a, b, c = map(int, input().split())
  roads.append((c, a, b))

# 유지비 기준으로 오름차순으로 정렬
quick_sort(roads, 0, m - 1)

answer = 0
for road in roads:
  cost, a, b = road
  
  # 한 마을을 구성하는데 cycle이 생기지 않으면
  if find_parent(parent, a) != find_parent(parent, b):
    # 두 집이 속한 집합들을 합친다.
    union_parent(parent, a, b)
    max_cost = cost
    answer += cost

# 마을 2개로 분리하기 위해 유지비가 가장 많이 드는 길 없애기
answer -= max_cost
print(answer)

に感銘を与える
リストに組み込まれたソート方法に慣れ、今はクイックソートコードを書きたいのですが、覚えていないので、直接ソートコードを書いて問題を解きました.
ライブラリで実装されているデータ構造やアルゴリズムに関連するコードをたまに作成するとよい.