2017/06/13 썸네일형 리스트형 BOJ)1396 크루스칼의 공 문제: icpc.me/1396 lca를 이용하는 난이도 있는 문제다. 풀이 방법이 재밌다. x정점에서 y정점으로 이동할 때의 최소온도는 도로네트워크 등의 문제에서 했듯이 두 정점 사이의 lca를 구해나가면서 해당 간선의 가중치의 최댓값도 parent 배열과 같이 저장하는 방법으로 구해낼 수 있으나 공이 움직일 수 있는 범위를 출력하는게 문제가 되었다. 오래 생각해도 모르겠어서 찾아보니까 재밌는 방법으로 이걸 해결할 수 있었다. MST를 구성하는 과정에서 두 정점을 연결하는 대신 새로운 정점을 생성하는 방법이다. 즉 기존의 정점들은 새로운 그래프에서의 leaf가 되며 n-1개의 정점을 새로 구축하는 방법이다. 예제의 그래프를 새로 구축하면 이런 모양이 될 것이다. (기존의 정점(1~5)) 여기서 새로 생기.. 더보기 이전 1 다음