최소신장트리. [1647]

[1. 문제 설명]

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

---

[2. 풀이 접근]

하나의 마을에서 집들을 연결하는 도로 => 그래프로 모델링 할 수 있다.

모든 집들이 연결 된 하나의 그래프를 두개의 그래프로 절단해야 한다.

•  단, 절단 된 두 마을의 유지비의 합을 최소로 해야한다.

여기서 다소 헷갈릴만한(?) 문구가 있는데,

• 임의의 두 집 사이에 경로가 항상 존재해야 한다.

이 문장은 하나의 마을을 두 개의 마을로 절단해야 할 때,

두 마을에는 적어도 두개의 집이 있어야 한다라고 생각이든다.

하나의 마을

절단 된 두개의 마을

그러나, 예제의 정답을 보면 이런 형태가 아니어도 상관 없는 것 같다.

예제에서 최소 유지비로 모든 집들을 연결하는 그래프 모양

이 중 유지비가 제일 큰 7<->6 edge 제거

그래서 문제가 좀 단순화되어 아래와 같이 정답을 구할 수 있다.

• 크루스칼 알고리즘 등을 이용하여 MST 를 구성
  => MST 의 전체 유지비를 알 수 있다.
• 이 MST 에서 유지비가 제일 큰 edge 를 제거,
  => 이 edge 의  유지비를 전체 유지비에서 제외하도록 한다.

---

[3. 코드]