import sys
input=sys.stdin.readline
def Find(x):
if x!=disjoint[x]:
disjoint[x]=Find(disjoint[x])
return disjoint[x]
N,M=map(int,input().split())
disjoint=[ _ for _ in range(N+1) ]
edge=[ list(map(int,input().split())) for _ in range(M) ]
edge.sort(key=lambda x:x[2])
total=0
check=0
for x,y,value in edge:
x=Find(x)
y=Find(y)
if x!=y:
if x>y:
disjoint[x]=y
else:
disjoint[y]=x
total+=value
check=max(check,value)
print(total-check)📌 어떻게 접근할 것인가?
최소 스패닝 트리 문제입니다. 저는 크루스칼 알고리즘을 통해 풀었습니다.
문제에서 중요한 것은
- 도시를 두 마을로 나누어서 간선의 비용이 최소가 되려고 한다.
즉 도시를 두 마을로 연결하는 것입니다. 크루스칼 알고리즘은 모든 노드들을 연결하는 알고리즘이기 때문에 생각을 해봐야합니다.
간단하게 모든 간선들을 최소의 비용으로 연결하고 가장 비용이 높은 간선 하나를 자르면 됩니다.
다만 이때 단순히 모든 간선들을 생각해서는 안되고 사이클이 발생하지 않아야 하기 때문에
if Finx(x)!=Find(y) 라는 조건일때 최대값을 찾아주어야 합니다.
