Joonas' Note

Joonas' Note

BOJ 3640 - 제독 본문

알고리즘/문제 풀이

BOJ 3640 - 제독

2020. 5. 24. 21:07 joonas

    링크: https://www.acmicpc.net/problem/3640

    문제

    가중치가 있는 방향 그래프가 주어지고, 1번 정점에서 V번 정점까지 서로 겹치지 않는 2개의 경로 중 비용이 최소인 경우를 출력하는 문제이다.


    겹치지 않는 경로를 찾는 것은 최대 유량으로 해결 가능하고, 그 비용이 최소가 되는 것을 구해야하므로, 네트워크 플로우 유형 중에서 MCMF(Min Cost Max Flow; 최소 비용 최대 유량)인 문제이다.


    그래프 문제는 항상 문제 조건을 꼼꼼히 살펴야겠다.

    이번에도 "출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안 된다." 에서 정점이 겹쳐서는 안되는 조건을 깜빡해서 계속 틀렸다.


    이 조건을 무시하면 틀리는 예외 케이스는 아래와 같다.

    최대 유량은 1개이고, 답은 4.

    5 6
    1 2 5
    1 3 2
    2 3 3
    3 4 4
    3 5 2
    4 5 3


    정점이 겹치면 안되므로, 정점을 분할하여 해결하면 된다.

    코드


    Comments