[BOJ 11408] - 열혈강호 5 (최대 유량, 최소 비용 최대 유량, Python)

보양쿠·2022년 9월 5일

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

BOJ

목록 보기

12/252

MCMF 연습 시리즈

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

도시 왕복하기 2에 이어서 열혈강호 5를 풀이해보겠다.

BOJ 11408 - 열혈강호 5 링크
(2022.09.05 기준 P3)
(치팅하면 정말 속상해)

문제

N명의 직원과 M개의 일이 있고, 각 직원은 일 하나만, 각 일은 한 명만 담당해야 한다면
가능한 일의 최대 개수 그리고 그 때 지불해야 할 최소 월급

알고리즘

시작부터 직원과 일을 거쳐 끝으로 흐르는 데이터의 수를 찾으므로 최대 유량인데
그 와중에 간선 별로 비용이 있으므로 최소 비용 최대 유량

풀이

이제 그냥 최대 유량이 아니다. 비용을 최소화 하는 최대 유량을 찾아야 한다.

벨만-포드를 공부하다 보면 알게 되는 알고리즘 'SPFA' 라는 것이 있다.
몰라도 된다. 이제 배우면 되니깐.

SPFA는 벨만-포드 알고리즘을 업그레이드 시킨 느낌인데, 갱신되는 점에 연결되어 있는 간선을 이용하여 정점에 대한 비용을 갱신할 때에 큐에 없다면 큐에 그 정점을 넣어주는 방식이다.
 procedure Shortest-Path-Faster-Algorithm(G, s)
  1    for each vertex v ≠ s in V(G)
  2        d(v) := ∞
  3    d(s) := 0
  4    push s into Q
  5    while Q is not empty do
  6        u := poll Q
  7        for each edge (u, v) in E(G) do
  8            if d(u) + w(u, v) < d(v) then
  9                d(v) := d(u) + w(u, v)
 10                if v is not in Q then
 11                    push v into Q
 #출처 위키피디아
아예 처음 접한다면, 구글링하여 학습한 뒤, 타임머신 문제를 SPFA로 풀어본 뒤에 다시 돌아오자.

공부할 때 이 링크도 좋음

이를 어떻게 이용하느냐.
기본 최대 유량 알고리즘은 유량을 흘리면서 증가 경로가 없어질 때까지 찾는 것인데, 이제는 이 과정에서 비용(가중치)를 두어 최단 경로를 찾아가는 것이다.
근데, 비용이 음의 가중치가 필요하다. 왜냐 하면, 역방향 간선일 때에 비용도 음의 비용으로 설정해야 하기 때문이다.
그래서 다익스트라는 불가능하고 벨만-포드나 SPFA를 사용하는 것인데, 벨만-포드보다 SPFA의 예상 소요 시간이 더 짧기 때문에 SPFA를 쓰는 것이다.

SPFA를 사용하여 용량과 유량 그리고 거리값에 따라 정점들을 갱신해주면서 끝 지점이 갱신이 되었다면 우리가 알고 있는 방식대로 유량을 찾아 흘리면 된다.
이 때, 비용을 구해야 한다면 유량을 끝에서부터 차례대로 흘릴 때, 그 간선의 비용을 출력값에 더해주면 된다.

코드

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

def solve():
    N, M = map(int, input().split())
    
    # 시작은 0, 끝은 N + M + 1
    start = 0; end = N + M + 1; length = end + 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)]

    for i in range(1, N + 1):
        # 시작과 직원을 연결
        # 각 직원은 한 개의 일만 할 수 있으므로 용량은 1
        connect[start].append(i)
        connect[i].append(start)
        capacity[start][i] = 1

        n, *lst = map(int, input().split())
        for k in range(0, n * 2, 2):
            j = lst[k] + N; c = lst[k + 1] # 일의 번호는 직원 수만큼 더해줘야 한다.
            connect[i].append(j)
            connect[j].append(i)
            capacity[i][j] = 1
            cost[i][j] = c
            cost[j][i] = -c # 역방향 간선의 비용은 음의 비용으로 설정

    # 일과 끝을 연결
    # 각 일을 담당하는 사람은 1명이므로 용량은 1
    for i in range(N + 1, N + M + 1):
        connect[i].append(end)
        connect[end].append(i)
        capacity[i][end] = 1

    answer = [0, 0] # 일의 개수와 월급의 최솟값
    while True:
        # 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

        # 끝 지점이 갱신이 되지 않았다면 경로가 없는 것이므로 break
        if prev[end] == -1:
            break
        # 유량은 어차피 1
        here = end
        while here != start:
            flow[prev[here]][here] += 1
            flow[here][prev[here]] -= 1
            answer[1] += cost[prev[here]][here] # 간선의 비용만큼 월급을 줘야 함
            here = prev[here]
        answer[0] += 1 # 유량이 처음에서 끝으로 흐른건 한 직원이 한 일을 할 수 있다는 것을 뜻함
    print(*answer, sep = '\n')

solve()