문제 링크

도시 분할 계획

문제 링크

마을은 N개의 집과 각각의 집을 연결하는 M개의 길로 이루어져 있다. 길은 양방향이다. 마을의 이장은 마을을 2개로 분할하려고 한다. 분할된 각 마을의 모든 집은 길로 연결되어야 할때, 길의 유지비를 최소로 하는 방법은?

문제 설명

이 문제는 최소 신장 트리를 구하는 문제이다. 다른 점은 최소 신장 트리를 한 그래프에서 두개 구해야 된다는 점이다. 그래프 내에서 하나의 신장트리를 일단 구하고, 그 그래프에서 가장 cost가 비싼 길을 제외하면 두개의 신장 트리를 찾을 수 있다. 최소 신장 트리를 구하는 방법은 크루스칼 알고리즘을 사용했다.

import sys

input = sys.stdin.readline

def find(parents, x):
    if parents[x] != x:
        parents[x] = find(parents, parents[x])
    return parents[x]

def union(a, b):
    a = find(parents, a)
    b = find(parents, b)
    if a > b:
        parents[a] = b
    else:
        parents[b] = a

n, m = map(int, input().split())
parents = [i for i in range(n+1)]
roads = []
result = 0
last = 0

for _ in range(m):
    a, b, cost = map(int, input().split())
    roads.append([cost, a, b])
roads.sort()

for road in roads:
    if find(parents, road[1]) != find(parents, road[2]):
        union(road[1], road[2])
        result += road[0]
        last = road[0]
print(result-last)