2463_비용
https://www.acmicpc.net/problem/2463
2463번: 비용
첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸
www.acmicpc.net
문제 이해 )
그래프가 주어지고 Cost(u, v)를 구하는 문제. Cost(u, v)에 경로가 없을 때까지 더 해진 그래프에 가중치의 최솟값들.
하지만 U<V 인 모든 cost를 구해야 하고 edge와 node의 값이 각 10만 개.... 단순한 방법으로는 해결이 불가능,
새로운 아이디어를 계속 탐구.
접근1) 단순한 방법의 접근!
먼저 알고리즘 분류로 찾은 문제라서 union find를 이용하는 방법으로 생각했지만 o(n^2)의 아이디어에서 막힘.
처음에는 cost의 규칙에 따라서 값을 구하다 보면 특정 패턴이 나올 것을 예측했지만 생각보다 쉽지 않음.
접근 2 ) MST
일단 모든 그래프가 연결된 상태를 만드는 것이 필요하다고 생각했고 MST를 구하면 각 노드의 cost를 알 수 있지 않을까?
하지만 역시
각 노드들에서 모든 cost를 구해야 하기 때문에 시간 복잡도 적인 측면에서의 한계는 분명 존재.
시간복잡도자체가 힌트가 아닐까? 생각 후에 다른 노드들과 연결 시 특정 패턴을 파악하려 노가다를 시작.
edge의 값이 높은 노드부터 확인하다 특정 패턴을 발견.
1. cost(3,6) = 45...
2. cost(1,2) = 35 ...
3. cost(2 ,6) = 29!
3번에서 cost(2,6)를 구하게 되면 cost(6,1) , cost(3,1), cost(3,2)의 값도 값이 cost(2,6) 임을 발견!
접근 3) new_idea !
sum_edge = edge의 총비용
rank [] = 각 집합의 개수
sum_cost = cost(u, v)의 합 (u <v)
1. MST의 반대의 개념으로 가장 높은 가중치의 edge를 찾아 x, y가 다른 집합이라면 union()
2. 이때 sum_cost의 값에 해당 edge가중치 *(rank [x] * rank [y)를 더해주자.
3. 같은 집합이면 pass.
추가)
원래는 모든 노드가 연결되면 종료했지만 그냥 모든 egde를 확인하니 성공함.
테스트 케이스에 모든 노드가 연결되어있지 않은 그래프가 존재하는 것 같음.
정답 : 34
코드 )
