2610. 회의준비

오랜만에 문제 풀이를 쓴다. 요즘 바빠서;;

2610번: 회의준비

---

위원회 구성

우선 위원회를 구성해야 한다. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 하므로, Union-Find를 이용하여 위원회를 구성할 수 있다. 서로 알고 있는 사람끼리 ``merge``한 다음, 각 참석자 ``i``를 ``root(i)`` 쪽으로 모은다.

대표 결정하기

대표를 결정하려면 우선 두 사람 사이의 의사전달시간을 알아야 한다. 매번 BFS 등으로 탐색하면 매우 비효율적이므로, 플로이드-와샬 알고리즘을 사용하여 임의의 두 사람 사이의 의사전달시간을 미리 계산해 두자.

 

그 후에는 의사전달시간의 최댓값이 최소가 되도록 하는 대표를 찾으면 된다. 간단하죠?

 

주의! 의사전달시간의 합이 최소가 되도록 하면 안 된다.

---

깔끔.