[BOJ] 1647. としぶんかつけいかく

質問する

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

入力

1行目は家の個数N,道の個数Mを与える.Nは2以上100000以下の整数、Mは1以上100000以下の整数である.次の行から、M行では、道の情報にABCの3つの整数が与えられ、A号家とB号家を結ぶ道の維持費がC(1≦C≦1000)であることを示す.

しゅつりょく

1行目を外し、残りの道路料金プロトコルの最高値を出力します.
最小伸長ツリーを2つ作成する必要があります.
最小限の費用で2本の成長木に分割しなければならない.
->クルーズアルゴリズム最小腎樹を探して、最小腎樹を構成する主幹線の中で最もコストの高い主幹線を除去します!

# 길의 유지비 합 최소로 구하기

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

arrays = []
result = 0 # 없애고 남은 길 유지비 합
parent = [0] * (n + 1) # 부모테이블 
for i in range(n + 1):
  parent[i] = i  # 부모테이블 자기 자신으로 초기화

for _ in range(m):
  a, b, c = map(int, input().split())
  # a번 집과 b번 집을 연결하는 길의 유지비 c
  arrays.append((a, b, c))

def sort_cost(arr):
  return arr[2]

arrays.sort(key = sort_cost) # 유지비용 기준으로 오름차순 정렬
# print(arrays)

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[b] = a
  else:
    parent[a] = b

for i in arrays:
  a, b, c = i
  if find_parent(parent, a) != find_parent(parent, b):
   # 서로 집합이 다르면 합치기
   union_parent(parent, a, b)
   result += c
   last = c

print(result - last)
# result 는 모든 집이 한 마을에 있는 것, 
# 두 마을로 나누고 유지비합이 최소가 되려면 가장 큰 비용의 길을 다른 마을로 바꾸면 됨