백준 2463번 비용

< 백준 2463번 비용 - 마포 코딩박 >

사용한 알고리즘: Union-Find


 문제에서 Cost(u,v) 는 최소 간선부터 제거하면서 u,v 가 다른 component 일 때 까지 제거되는 간선의 합입니다. 이때 u<v 인 모든 정점 u,v 에 대해 Cost(u,v) 들의 총 합을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (생각)
 거꾸로 생각하여 모든 정점이 분리되어 있고, 최대 간선부터 차례로 연결하며 해당 간선을 연결하여 같은 component 가 되는 정점 u, v 에 대해 볼 것입니다.
 문제에서 주어진 예시를 예로 들면,
 1. 초기 6개의 정점은 따로 떨어져 있고 모든 간선의 합은 45 입니다.
 2. 먼저 최대 간선인 15 를 연결하면 정점 3, 6은 하나의 component가 되고, 따라서 Cost(3,6) = 45 입니다. 이후 남은 모든 간선의 합은 30 입니다.
 3. 이 다음 최대 간선 10을 연결하면 정점 1, 2는 하나의 component가 되고 Cost(1, 2) = 30 입니다. 이후 남은 모든 간선의 합은 20 입니다.
 4. 이 다음 최대 간선 6을 연결하면 정점 1,3 / 1,6 / 2,3 / 2,6 은 하나의 component가 되고 Cost(1,3) = Cost(1,6) = Cost(2,3) = Cost(2,6) = 20 입니다. 이후 남은 모든 간선의 합은 14입니다.
 위 과정을 남은 간선이 없을때 까지 반복하면 됩니다.

(2) (코드 10~22)
 입력되는 정점 a, b 를 있는 간선의 가중치 w 를 하나의 struct로 vector에 저장합니다. 이후 가중치가 큰 간선부터 차례로 볼 것입니다.

(3) (코드 23~43, 63~75)
 최대 가중치와 그에 연결되는 정점 a,b 를 차례로 보며 다음 과정을 진행합니다.
 Union-Find 로 a,b 의 component를 확인하고, 둘이 다른 component 일 경우, 두 component에 포함된 정점 수 각각 찾습니다.
 이 두 정점수를 곱해 새로 만들어지는 Cost(u,v) 개수를 찾고, 이에 남은 모든 간선의 합을 곱해 구하고자 하는 답에 추가합니다.