6497: 전력난

문제 링크

6497: 전력난

구현 방식

• 매 TC마다 MST를 구해주고, 모든 간선들의 가중치 합에서 MST내 간선들의 가중치 합을 빼준 값이 절약할 수 있는 최대 비용이 된다

코드

import sys

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

def union(a, b):
    a = find(a); b = find(b)
    if a < b: parent[b] = a
    else: parent[a] = b

while True:
    M, N = map(int, sys.stdin.readline()[:-1].split())
    if (M, N) == (0, 0): break

    edges = []; tc = 0
    for n in range(N):
        x, y, z = map(int, sys.stdin.readline()[:-1].split()); tc += z
        edges.append((x, y, z))

    edges.sort(key=lambda x:x[2])
    parent = [i for i in range(M)]

    mtc = 0
    for edge in edges:
        u, v, cost = edge
        if find(u) != find(v):
            mtc += cost; union(u, v)
    print(tc - mtc)