[BOJ]11085번: 군사 이동

 

문제: https://www.acmicpc.net/problem/11085

---

스패닝 트리문제입니다. 크루스칼로 해결할 수 있습니다.

 

두 정점을 연결하는 간선들 중 최소비용이 최대가 되게 하려면 가장 큰 간선부터 PQ에서 뽑아 그래프를 연결합니다.

 

그리고 두 정점이 연결되는지 계속 체크합니다.

 

특정 간선이 뽑히고 두 정점이 처음으로 연결된다면 그 간선이 최소비용이 최대가 되게 하는 정답입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ11085.cc