BOJ - 6497 - 전력난

Updated:

import sys
import heapq

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

def unionx(parent, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if not rootX == rootY: parent[rootY] = rootX

def solution():
    while True:
        M, N = map(int, sys.stdin.readline().split())
        if M == N == 0: break
        hq = []
        heapq.heapify(hq)
        parent = [i for i in range(M)]

        total, ans = 0, 0

        for _ in range(N):
            x, y, z = map(int, sys.stdin.readline().split())
            heapq.heappush(hq, (z, x, y))

        while hq:
            weight, start, end = heapq.heappop(hq)
            total += weight
            if find(parent, start) != find(parent, end):
                unionx(parent, start, end)
                ans += weight
        print(total - ans)

solution()

https://www.acmicpc.net/problem/6497

Categories:

Updated:

Leave a comment