최대 비용을 가지는 신장 트리를 만드는 방법?

1. 문제

 

7044번: Bad Cowtractors (acmicpc.net)

7044번: Bad Cowtractors

 

2. 풀이

 

문제를 보면... 비용이 최대가 되는 신장 트리를 만들때, 그 비용을 출력하라는 문제

 

최소 신장 트리는 들어봤는데 최대 신장 트리는 뭔데

 

순간 당황

 

근데 크루스칼 알고리즘에서 (비용,간선)을 담고 비용의 오름차순으로 정렬한 다음에..

 

하나씩 빼서 신장 트리를 만드는 점에 착안해서

 

내림차순으로 정렬해서 하나씩 빼가지고 신장 트리를 만든다면... 최대 비용을 가지는 신장 트리를 만들 수 있는게 아닐까?

 

근데 진짜 되더라고.. 허허

 

여기서 신장 트리를 구성하지 못한다면 -1을 출력하라고 하던데..

 

신장 트리를 구성할 조건은 n-1개의 간선을 선택했느냐이다...

 

그래서 for문을 전부 돌더라도 선택한 간선의 수가 n-1이 아니라면 신장 트리를 구성하지 못했으므로 -1을 출력해야한다

 

from sys import stdin

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

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

    if parent[a] < parent[b]:
        
        parent[b] = a
    
    else:
        
        parent[a] = b
    
n,m = map(int,stdin.readline().split())

edges = []

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    edges.append((c,a,b))

parent = [i for i in range(n+1)]

#최대 비용을 가지는 신장 트리를 만들기 위해
#내림차순으로 정렬
edges.sort(reverse=True)

answer = 0
count = 0

for c,a,b in edges:

    if find_parent(a,parent) != find_parent(b,parent):

        union(a,b)
        count += 1
        answer += c

    if count == n-1:

        break

#n-1개의 간선을 선택하지 못했다면..
#모든 간선을 확인해봐도.. 신장 트리를 구성하지 못했다
if count != n-1:

    print(-1)

else:

    print(answer)