BOJ 14621(나만 안되는 연애)풀이

solved.ac 티어 : 골드 3

www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

 

이문제는 기본 mst(최소 스패닝 트리)에서 간선을 추가할 때 두 점이 다른 점이라면 추가하는 방식으로 하면 된다.

그리고 마지막에 -1 처리를 해주면 된다.

import sys
sys.setrecursionlimit(10**9)
def find(a):
    if uf[a]<0:return a
    uf[a]=find(uf[a])
    return uf[a]
def merge(a,b):
    a=find(a)
    b=find(b)
    if a==b:return 0
    uf[b]=a
    return 1
input=sys.stdin.readline
n,m=map(int,input().split())
ch=[0]*(n+1)
l=list(input().strip().split())
e=[]
for i in range(m):
    b,c,d=map(int,input().split())
    if l[b-1]!=l[c-1]:e.append([d,b,c])
#print(e)
e.sort()
rt=0
cnt=0
uf=[-1]*(n+1)
m=len(e)
gh=0
for i in range(m):
    if merge(e[i][1],e[i][2]):
        rt+=e[i][0]
        cnt+=1
        if cnt==n-1:gh=1;break
if gh==0:print(-1)
else:print(rt)