이동식 저장소

코로나 새내기들에게 꼭 필요한 문제

학교 지도가 연결 그래프로 주어진다. 학교의 모든 건물을 탐방하는 경로 중 피로도가 최대일 때와 최소일 때의 차이를 구해야 한다. 피로도는 지나간 오르막길의 개수의 제곱으로 계산하므로, 오르막길을 가장 많이(또는 적게) 지나가는 경우를 구해야 한다.

건물 $N$개와 입구까지 총 $N+1$개의 노드를 연결하는 트리에는 간선이 $N$개 존재한다.

지문은 거창하지만, 그냥 최소 스패닝 트리 문제이다. 피로도가 최대인 경우를 계산하려면 오르막길과 내리막길의 가중치를 각각 0과 1로 두고 MST를 만들면 된다. 만든 MST의 가중치의 합은 내리막길의 수와 같으므로, 구한 값을 $N$에서 빼면 오르막길의 개수를 구할 수 있다. 이 값을 $h_1$이라 하자.

피로도가 최소인 경우를 계산하려면 오르막길과 내리막길의 가중치를 서로 바꿔서 계산하면 된다. 그러면 MST에 포함되는 오르막길의 수를 바로 구할 수 있다. 이 값을 $h_2$라 하자.

마지막으로 $(h_1{)}^2-(h_2{)}^2$를 출력하기만 하면 된다. 참 쉽죠?

재밌어 보여서 골랐는데, 그냥 구현 문제였네..