BOJ 4792 - 레드 블루 스패닝 트리

문제 링크(Link)

---

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

문제 해결(Solution)

---

 MST를 두 번 생성해서 문제를 해결할 수 있다.

 1. min_blue : R 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수

 2. max_blue : B 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수

 3. Answer : min_blue <= K <= max_blue ? 1 : 0

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 왜 "min_blue <= K <= max_blue ? 1 : 0" 가 성립하는가?

  : R 간선을 우선으로 MST를 생성할 때 필요한 B 간선은 spanning tree를 생성하는 데에 있어서 반드시 필요한 간선이다. 즉, MST 생성 과정에서의 최소한의 필요한 B 간선의 개수는 min_blue가 된다. 반대로 B 간선을 우선으로 MST를 생성할 때 사용되는 B 간선은 MST 생성 과정에서의 최대한의 필요한 B 간선의 개수이며, 그 것은 max_blue가 된다.

 2. 시간 복잡도는? 

  :  그래프의 정렬 과정에 소요되는 O(NlgN)이 지배적이다.

참고(Reference)

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.