[백준] 나만 안되는 연애

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

14621번: 나만 안되는 연애

대학에서 다른 대학으로 모두 이동이 가능해야하고 모든 간선의 합이 최소가 되어야하므로 최소 스패닝 트리를 찾아야함을 알 수 있습니다. 조건에 의해 남초 - 남초, 여초 - 여초를 연결하는 간선은 힙에 넣지 않고 크루스칼을 돌리면 됩니다. 그리고 마지막에 모든 정점들이 같은 집합에 속해있는지만 체크해주면 됩니다.

 

import sys, heapq

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

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

status = ['X'] + list(input().split())

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

q = []
for _ in range(m):
    v1, v2, w = tuple(map(int, input().split()))
    # 같은 대학끼리는 넘어간다.
    if status[v1] == status[v2]:
        continue

    heapq.heappush(q, (w, v1, v2))

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

    parent[p] = find(parent[p])
    return parent[p]

ans = 0

# 크루스칼
while q:
    w, v1, v2 = heapq.heappop(q)
    pa = find(v1)
    pb = find(v2)

    if pa == pb:
        continue

    ans += w

    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb

cur = find(parent[1])

for p in parent[2:]:
    # 모든 대학이 같은 집합에 있지 않으면 -1을 출력
    if cur != find(p):
        print(-1)
        sys.exit(0)

print(ans)