[BOJ 3640] - 제독 (최대 유량, 최소 비용 최대 유량, Python)

보양쿠·2022년 9월 5일

boj 최대 유량 최소 비용 최대 유량

BOJ

목록 보기

13/252

MCMF 연습 시리즈

BOJ 2316 - 도시 왕복하기 2 (정점 분할) 풀이
BOJ 11408 - 열혈강호 5 (최소 비용 최대 유량) 풀이
BOJ 3640 - 제독 (정점 분할 + 최소 비용 최대 유량) 풀이

드디어 연습 시리즈 마지막 문제 '제독'
바로 풀이를 시작해보겠다.

BOJ 3640 - 제독 링크
(2022.09.05 기준 P2)
(치팅은 정말 정말 속상해)

문제

v개의 지점과 e개의 뱃길이 있고 뱃길마다 지나기 위해 필요한 포탄 수가 있다고 했을 때
1번과 v번을 제외한 지점들을 겹치지 않게 지나는 1번과 v번 사이의 두 경로를 선택했을 때의 최소 포탄 수

알고리즘

지점이 겹치지 않게 -> 정점 분할 (도시 왕복하기 2)
최소 포탄 수 -> 최소 비용 최대 유량 (열혈강호 5)
이 두 문제를 섞어놓은 것이다.

풀이

앞에서 다루었던 두 문제. 도시 왕복하기 2, 열혈강호 5에서 나왔던 정점 분할과 최소 비용 최대 유량을 응용할 차례가 왔다.

1번부터 v번까지의 두 경로를 선택해야 하는데, 1번과 v번을 제외하면 지점이 겹치면 안된다.
이는 정점 분할하면 해결되는 문제다.
잘 모르겠다면 도시 왕복하기 2 풀이를 보고 오자.

두 경로를 선택할 때, 비용(포탄 수)이 최소가 되어야 한다. 이는 SPFA를 이용하여 정점들을 갱신하여 유량을 흘리면 된다.
잘 모르겠다면 열혈강호 5 풀이를 보고 오자.

이 때, 경로가 없을 때까지 찾으면 안된다. 2개의 경로를 찾는 것이기 때문.
그러므로 간단하게 for문으로 두 번 돌려주자.
v번이 갱신이 안되면 어떡하지 라는 걱정은 버리자.

주의사항

EOF 처리는 꼭 해주자.

코드

import sys; input = sys.stdin.readline
from collections import deque
from math import inf

def solve():
    v, e = map(int, input().split())

    # 정점 분할
    # in 노드는 i, out 노드는 i + v
    # 그러므로 전체 필요한 정점 수는 v * 2 + 1 (1번부터 시작할 것이므로 1을 더해야 함)
    length = v * 2 + 1
    flow = [[0] * length for _ in range(length)]
    capacity = [[0] * length for _ in range(length)]
    cost = [[0] * length for _ in range(length)]
    connect = [[] for _ in range(length)]
    # in과 out을 연결
    for i in range(1, v + 1):
        connect[i].append(i + v)
        connect[i + v].append(i)
        capacity[i][i + v] = 1
    # 길의 양 정점을 in과 out을 잘 구분하여 연결
    # 방향성이 있는 간선이므로 a -> b만 연결하자
    for _ in range(e):
        a, b, c = map(int, input().split())
        connect[a + v].append(b)
        connect[b].append(a + v)
        capacity[a + v][b] = 1
        cost[a + v][b] = c
        cost[b][a + v] = -c

    # 시작은 out이므로 1 + v
    # 끝은 in이므로 v
    start = 1 + v; end = v
    answer = 0
    for _ in range(2): # 경로를 2개 찾아야 하므로 두 번만 돌림
        #SPFA
        prev = [-1] * length
        distance = [inf] * length
        q = [False] * length
        queue = deque([start])
        distance[start] = 0
        q[start] = True
        while queue:
            here = queue.popleft()
            q[here] = False
            for there in connect[here]:
                if capacity[here][there] - flow[here][there] > 0 and distance[there] > distance[here] + cost[here][there]:
                    distance[there] = distance[here] + cost[here][there] # 거리 갱신
                    prev[there] = here # prev 갱신
                    if not q[there]: # 큐에 없다면 넣어준다.
                        queue.append(there)
                        q[there] = True

        ''' # 1과 v 사이엔 겹치지 않는 경로가 최소 두 개 있다고 문제에 나와 있으므로 이 if문은 필요 없다.
        if prev[end] == -1:
            break
        '''
        # 유량은 어차피 1
        here = end
        while here != start:
            flow[prev[here]][here] += 1
            flow[here][prev[here]] -= 1
            answer += cost[prev[here]][here]
            here = prev[here]
    print(answer)

while True:
    try:
        solve()
    except:
        break