백준(BOJ) 14950 정복자(Python)

문제 내용.

 

MST 문제.

간단하게 MST의 크기를 구한 후 (n-2)*(n-1)*t/2를 더해주면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

n,m,t=map(int,input().split())
parent=[i for i in range(n+1)]

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

def union(x,y):
    x=find(x)
    y=find(y)
    x,y=min(x,y),max(x,y)
    if x!=y:
        parent[y]=x
        return 1
    return 0


heap=[]
heapq.heapify(heap)
for i in range(m):
    a,b,c=map(int,input().split())
    heapq.heappush(heap,[c,a,b])
count=0
ans=0


while count<n-1:
    c,a,b=heapq.heappop(heap)
    if union(a,b):
        count+=1
        ans+=c
print(ans+(((n-2)*(n-1))//2)*t)

정복자 너프해라