백준14166 Robotic Cow Herd

작성일 | In

문제 링크

  • http://icpc.me/14166

문제 출처

  • USACO 2016 December Platinum 3번

사용 알고리즘

  • Eppstein algorithm

시간복잡도

  • $O(E \log V + K \log K)$
  • 이때 $V=NM+N+1, E=2NM$

풀이

만약 모든 부품이 다른 로봇을 만들어야 한다면 Layer를 $N$개 쌓은 그래프에서 MCMF로 해결할 수 있습니다. 하지만 이 문제는 한 부품만 달라도 되기 때문에 플로우를 이용해 해결할 수 없습니다. 동일한 그래프 모델링을 활용해 다른 알고리즘으로 해결할 수 있을지 고민해 봅시다.

이 문제는 Layer를 $N$개 쌓은 그래프에서 가장 짧은 경로, 두 번째로 짧은 경로, … , $K$번째로 짧은 경로를 구하면 해결할 수 있습니다. 이러한 문제를 빠르게 해결할 수 있는 알고리즘으로는 Eppstein algorithm이 잘 알려져 있습니다. 이 알고리즘은 $1, 2, \cdots, K$번째 최단 경로의 길이를 $O(E \log V + K \log K)$ 시간에 구하는 알고리즘입니다.
우리가 최단 거리를 구하고자 하는 그래프는 $O(NM)$개의 정점과 $O(NM)$개의 간선으로 구성되어 있으므로 Eppstein algorithm을 이용해 $O(NM \log NM + K \log K)$ 시간에 문제를 해결할 수 있습니다.

Eppstein algorithm은 논문과 Good Bye, BOJ 2020! 풀이 슬라이드의 남부순환로 문제 해설에 잘 설명되어 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<Trio> E;
    int V = 0;
    for(int i=1; i<=N; i++){
        int M; cin >> M;
        for(int j=1; j<=M; j++){
            int t; cin >> t;
            E.emplace_back(V, V+j, t);
            E.emplace_back(V+j, V+M+1, 0);
        }
        V += M + 1;
    }
    K_Shortest G(E, V + 1, 0, V, K);
    long long R = 0;
    for(const auto &i : G.get()) R += i;
    cout << R;
}