joseph0528 코딩 블로그

요약하면 그래프가 주어지고, Q개의 쿼리에서 X, Y 가 주어지면 X, Y에서 시작하는 스패닝 트리의 최솟값을 구하라는 문제이다. 기존 스패닝 트리와는 다르게 두 점 X, Y에서 스패닝 트리가 시작할 수 있는데 이는 즉, 한 그래프 안에서 스패닝 트리가 2개가 나올 수도 있다는 소리가 된다. 그럼 이를 어떻게 해결할 수 있을까? 그 방법은 스패닝 트리의 특징을 생각해보면 알 수 있다. 스패닝 트리는 N개의 점에 대해 N-1 개의 간선을 가진다. 또 문제에선 X,Y 에서 시작하는 최소 스패닝 트리를 요구하기 때문에 N-1 간선에서 최대 1개의 간선을 제거할 수 있다. 간선을 2개 이상 제거 할 경우, 어떠한 점을 연결할 수 없게 된다. 그러므로 최대 선 1개만 지울 수 있다, 음수 가중치가 없기 때문에 선..