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

문제 풀이가 이해가 안되서 질문드립니다. 스패닝 트리 문제입니다.


문제 요약 : 노드가 N개인 완전 그래프에서 M(

이때 사용된 간선들의 가중치의 최댓값이 최소가 되도록 한다. 사용된 간선들의 가중치중 최댓값을 구하라.


풀이 : 크루스칼 알고리즘으로 그래프에서 M개의 간선으로 이루어진 최소 스패닝 트리를 만들고, 가장 마지막에 추가되는 간선의 가중치가 답이 된다.


이해가 안되는 점: MST는 '가중치의 합'이 최소가 되는 스패닝 트리로 이해하고 있다. 그런데 이 문제에서는 스패닝 트리를 이루는 '간선들의 가중치중 최댓값'을 최소로 하는 스패닝 트리를 MST로 보고있는 것 같다. 어째서?? 본인의 능지로는 MST가 왜 답이 되는지 이해가 안된다. MST가 아닌 다른 스패닝 트리가 답이 되는 경우는 없다고 확신할수가 없다. 


부디 능지처참한 글쓴이를 위한 조언을 해주십쇼