[백준] 정복자

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

14950번: 정복자

MST를 구하는 문제입니다. 프림, 크루스칼로 MST를 구한 다음 증가하는 비용만큼을 추가해주면 됩니다. N개의 노드에서 MST를 선택하면 N - 1개의 간선을 선택하게 되고 증가하는 비용의 총합은 0 ~ N - 2의 합 * t이므로 MST의 간선의 합에 추가적으로 더해주면 됩니다.

 

프림

import sys, heapq
from collections import defaultdict

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
graph = defaultdict(list)
INT_MAX = sys.maxsize

n, m, t = tuple(map(int, input().split()))

for _ in range(m):
    s, e, w = tuple(map(int, input().split()))
    graph[s].append((e, w))
    graph[e].append((s, w))

def prim(start):
    visited = [False] * (n + 1)
    dist = 0

    q = [(0, start)]
    while q:
        w, cur = heapq.heappop(q)

        if visited[cur]:
            continue

        visited[cur] = True
        dist += w

        for next, next_w in graph[cur]:
            if not visited[next]:
                heapq.heappush(q, (next_w, next))

    return dist

# 정복 과정에서 증가하는 도시 비용 추가
ans = prim(1) + ((n - 1) * (n - 2) // 2 ) * t
print(ans)

 

크루스칼

import sys
from collections import defaultdict

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
graph = defaultdict(list)
INT_MAX = sys.maxsize

n, m, t = tuple(map(int, input().split()))

edges = []
parents = [x for x in range(n + 1)]

for _ in range(m):
    s, e, w = tuple(map(int, input().split()))
    edges.append((w, s, e))


def find(p):
    if p == parents[p]:
        return p
    parents[p] = find(parents[p])
    return parents[p]

def kruskal():
    edges.sort()
    dist = 0

    for w, s, e, in edges:
        p_a = find(s)
        p_b = find(e)

        if p_a == p_b:
            continue

        dist += w

        if p_a < p_b:
            parents[p_b] = p_a
        else:
            parents[p_a] = p_b
    return dist


# 정복 과정에서 증가하는 도시 비용 추가
ans = kruskal() + ((n - 1) * (n - 2) // 2 ) * t
print(ans)