https://www.acmicpc.net/problem/1647
시간 2초, 메모리 256MB
input :
- N M (2 <= N <= 100,000)(1 <= M <= 1,000,000)
- A B C (1 ≤ C ≤ 1,000)
output :
- 첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.
조건 :
-
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다.
-
마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 마을에는 집이 하나 이상 있어야 한다.
-
마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.
분리된 마을 내부의 모든 집들을 연결되어야 하고 두개의 마을은 연결되지 않아야 한다.
가장 쉽게 분리하려면 크루스칼 알고리즘을 통해 우선적으로 모든 집을 연결하고 가장 긴 간선을 삭제하면 된다.
union-find를 통해서 간선을 n - 1개만 가지도록 하는 것도 괜찮은 방법이다.
import sys
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(one, two):
parent_one = find(one)
parent_two = find(two)
if parent_one < parent_two:
parent[parent_two] = parent_one
else:
parent[parent_one] = parent_two
n, m = map(int, sys.stdin.readline().split())
edge, parent, ans = [], [i for i in range(n + 1)], []
for i in range(m):
a, b, c = map(int, sys.stdin.readline().split())
edge.append((c, a, b))
edge.sort()
idx = 0
while len(ans) < n - 2:
cost, node_a, node_b = edge[idx]
if find(node_a) != find(node_b):
union(node_a, node_b)
ans.append(cost)
idx += 1
print(sum(ans))
