[BaekJoon] 백준 1647번 : 도시 분할 계획

1647번 : 도시 분할 계획

마을을 두 마을로 나누면서 최소한의 비용으로 유지하고 싶다면 우선 하나의 MST 를 만든 뒤 가장 비용이 비싼 길 하나를 지우면 된다.

그렇게 되면 마찬가지로 최소한의 비용으로 유지하는 두 마을을 만들 수 있다.

---

import sys


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

	return parent[node]


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


def solution():
	answer = 0
	parent = [i for i in range(node_cnt + 1)]
	edges.sort()

	for edge in edges:
		cost, start, end = edge
		if find_parent(parent, start) != find_parent(parent, end):
			union_parent(parent, start, end)
			answer.append(cost)

	return sum(answer[:-1])


if __name__ == "__main__":
	node_cnt, edge_cnt = map(int, input().split())
	edges = []
	for _ in range(edge_cnt):
		start, end, cost = map(int, sys.stdin.readline().rsplit())
		edges.append((cost, start, end))

	print(solution())