경로 압축 썸네일형 리스트형 BOJ)10637 Minimum Spanning Tree 문제: icpc.me/10637 간선들의 셋이 주어진다. 출력해야하는 답은 각 간선마다 자신을 제외한 간선들로 만들 수 있는 MST의 가중치의 합을 출력하는 문제이다. 이건 MST에 포함 안되는 간선에 대한 답은 MST의 가중치가 되겠지만 아닌 경우가 문제가 된다. 그렇다면 아닌 경우에 대해 생각해보자. 만약에 MST에 포함되지 않는 간선이 u-v 를 연결한다고 생각해보자 그러면 우리는 mst에서 u v를 잇는 경로상의 어떤 간선을 지워도 이 간선을 통하여 MST를 유지 할 수 있다. 즉 이러한 사실을 이용하여 MST를 만들 때 사용되지 않은 간선들을 가중치 순서대로 정렬하여 오프라인으로 미리 mst상에 사용 된 간선들의 답을 정해주는 것이다. 여기서 매번 경로를 확인해준다면 당연히 TLE를 보게 될 것.. 더보기 이전 1 다음