[추석맞이 폴란드 스터디] 180923

일의 우선순위를 정해야 하는 시점.

입시 + 시험공부 + NN스터디 + POI스터디 + QM스터디 + 그 사건 + CubbyMath + 졸업논문 + 과제 = ???

풀이 형식

문제 제목 : POI N / N+1 년의 경우 POI(N+1)으로 표기.

문제 난이도 : 일반적인 Codeforces 난이도 기준. Div2A~B, Div1A~D.

문제 분류 : 그 문제를 푸는 데 필요한 주관적인 KW.

문제 풀이 : (tmi가 포함된) 문제 풀이.

- 문제 요약이 없습니다. 첨부한 링크를 먼저 보고 와주세요.

오늘 푼 문제 (1 / Total 8)

POI04. 동굴 탐험 (Div1C)

---

---

POI04. 동굴 탐험

Tag : Multi-Source Dijkstra, Binary Expansion, Disjoint - Set Handling

실제로는 풀지 못한 문제고, jwvg0425님과 ko_osaga님의 디스커션을 참고했다.

그래프에서 source가 주어져 있을 때, source -> source의 non-trivial, simple cycle의 길이 최솟값을 구해야 한다. edge는 통과하는 방향에 따라 코스트가 바뀐다.

솔직히 별 생각 다 했다. 정점을 두 층으로 분리해서 다익스트라를 돌리나? 아니면 플로우인가? 해봤지만 AC에 다가갈 수조차 없었다.

우선 이 문제에서 고려할 변수를 'Shortest Path' 하나로 좁혀야 한다.

그래프에서 1번 정점을 빼고 생각하면, 결국 문제의 답은 다음과 같다. 솔직히 이 관찰조차 못한 내가 너무 한심했다.

$$ \min_{v \neq w} F(v,w) = \left(\text{Weight}[1 \to v] + \text{SP}[v \to w] + \text{Weight}[w \to 1]\right) $$

이제 문제가 얼추 APSP(All Pair Shortest Path)처럼 보인다. 

APSP를 V번 다익스트라로 그냥 구하면 \(O(VE\lg V)\)가 되고, 제한 시간 안에는 못 들어오는 모양이다.

뭐지? 그럼 \(O(E)\)짜리 SSSP(Single Source Shortest Path)를 짜라는 건가?

실제로 spfa도 노려볼 만한 solution이긴 하지만, 반례를 얼마든지 만들 수 있는데다 04년 문제를 상대로는 너무 추한 방법이다.

나라면 여기까지 와서도 Shortest path 접근을 포기했을 것 같다. 하지만 킹갓이 달리 킹갓이겠는가.

아이디어는 정점 집합을 2개의 서로소 집합 S, T로 분할하면 단 4번의 multi-source dijkstra로 모든 \((v,w) \in S \times T \cup T \times S\)에 대해 

$$ \min_{v \neq w} F(v,w) $$

를 구할 수 있다는 것이다. Multi-source dijkstra를 실제로 어떻게 구축하는지는 jwvg님의 블로그에 더 잘 설명되어 있다. 이 procedure 전체를 (S,T) - 분할이라 하자.

총 \(K\)번의 (S,T) - 분할로 모든 \(v \neq w\)에 대해 \(F(v,w)\)를 구하기 위해서는 각각의 분할에서 \(v\)가 속했던 집합들의 나열 \(T_{1}T_{2}\cdots T_{K}\)가 모두 달라야 한다. 그리고 잘 알려져 있듯, 이를 이진법으로 구현하면 \(K = \lg V\)면 충분하고, 동시에 최소이다.

이를 구현하는 방법은 간단하다.

i번째 (S,T) 분할에서는 i번째 비트가 켜져 있는 정점을 S, 꺼져 있는 정점을 T에 넣으면 된다.

전체 시간복잡도는 다익스트라 O(ElgV) * 분할 횟수 lgV = \(O(E \lg^{2} V)\)다.