[7211] Ringsõit

https://www.acmicpc.net/problem/7211

 

유니온 파인드의 기본 문제다.

---

풀이 방법

입력되는 간선 정보를 저장한다.

이때 국가소유의 간선인지 아닌지 또한 저장해야 한다.

 

간선정보를 비용순서로 정렬. 모든 단선을 탐색하며 유니온 과정을 수행한다.

• 해당 간선이 국가소유의 간선이며 최소 스패닝 트리에 포함되어야 하는 간선이라면 비용을 0으로 하여 필요한 비용으로 추가한다.
• 해당 간선이 국가소유의 간선이지만 최소 스패닝 트리에 포함하면 안 되는 간선이라면 해당 간선의 비용을 필요한 비용에서 빼준다.
• 국가소유의 간선이 아니라면, 최소 스패닝 트리에 포함되는지 여부를 확인한 뒤 필요한 비용에 반영하면 된다.

필요한 비용이 0보다 작다면 0을 출력. 그 이상이라면 해당 비용을 출력하면 된다.

---

정답 코드