다이아 찍고 산뜻하게 쉬운 최대 유량 문제를 풀어보았다.
재밌게 만드려고 한 티가 꽤 나는 문제라 풀이를 적어보겠다.

BOJ 17222 - 위스키 거래 링크
(2022.09.27 기준 P4)
(치팅 놉!)

문제

명진이가 명진이의 친구들한테 위스키를 주고, 명진이의 친구들과 주은이의 친구들이 위스키를 주고 받고, 주은이의 친구들이 주은이한테 위스키를 주는 유통망이 있다.
명진이의 친구들과 주은이의 친구들이 각각 한 명에게서 받을 수 있는 위스키의 양이 정해져 있을 때, 주은이가 받을 수 있는 최대 위스키의 양

알고리즘

위스키를 유량이라고 생각하면, 주은이한테로 얼마나 많은 유량이 흐르냐를 알아보는 문제다.
그러므로 간단한 에드몬드-카프 알고리즘을 사용하는 최대 유량 문제이다.

풀이

문제를 읽어서 파악해야 하는 정보가 있다. 이를 요약하자면

• 명진이가 보내는 위스키와 주은이가 받는 위스키의 양은 무제한
• 명진이는 명진이의 친구들이랑만, 주은이는 주은이의 친구들이랑만 연결되어 있다.
• 친구들끼리는 무조건 '명진이의 친구들 -> 주은이의 친구들'이 아니라 양방향도 가능하다. 그리고 친구들끼리 모두 연결되어 있지 않다.
• 위스키의 제한은 각각 한 명이 받을 수 있는 위스키의 전체 양이 아니라 한 명으로부터 최대로 받을 수 있는 위스키의 양이다.

이를 그림으로 쉽게 나타내면

이렇게 된다.

위 그림대로 모델링을 하여 최대 유량을 찾아주면 그 최대 유량이 즉, 주은이가 받을 수 있는 위스키의 최대 양이 된다.

코드

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

N, M = map(int, input().split()) # 명진 친구 - N + 1 ~ N + M, 주은 친구 - 1 ~ N
source = 0; sink = N + M + 1; length = sink + 1 # 명진 - source, 주은 - sink
jf = list(map(int, input().split()))
mf = list(map(int, input().split()))
whisky = [0] + jf + mf # 주은과 명진의 친구들의 위스키 제한

# source -> 명진 친구들 <-> 주은 친구들 -> sink
# 'source -> 명진 친구들', '주은 친구들 -> sink'를 이어주자.
# 용량은 'source -> 명진 친구들'은 명진 친구들의 위스키 제한으로
# '주은 친구들 -> sink'은 무한대로 두자.
connect = [[] for _ in range(length)]
capacity = [[0] * length for _ in range(length)]
flow = [[0] * length for _ in range(length)]
for i in range(N + 1, N + M + 1): # source -> 명진 친구들
    connect[source].append(i)
    connect[i].append(source)
    capacity[source][i] = whisky[i]
for i in range(1, N + 1): # 주은 친구들 -> sink
    connect[i].append(sink)
    connect[sink].append(i)
    capacity[i][sink] = inf

# 명진이의 친구들 순서대로 연결된 사람들이 주어진다.
for i in range(N + 1, N + M + 1):
    K, *callables = map(int, input().split())
    for j in callables:
        connect[i].append(j)
        connect[j].append(i)
        capacity[i][j] = whisky[j]

answer = 0 # 주은이가 전달받은 위스키의 양
while True: # 에드몬드-카프 시작
    # sink로의 길을 BFS로 찾기
    prev = [-1] * length
    queue = deque([source])
    while queue:
        here = queue.popleft()
        if here == sink:
            break
        for there in connect[here]:
            if capacity[here][there] - flow[here][there] > 0 and prev[there] == -1:
                prev[there] = here
                queue.append(there)
    if prev[sink] == -1:
        break
    # 흐를 수 있는 최대 유량 찾기
    f = inf
    here = sink
    while here != source:
        f = min(f, capacity[prev[here]][here] - flow[prev[here]][here])
        here = prev[here]
    # 찾은 유량을 흘리기
    here = sink
    while here != source:
        flow[prev[here]][here] += f
        flow[here][prev[here]] -= f
        here = prev[here]
    answer += f
print(answer)

여담

난 영어를 잘 못해서, 적당한 변수 이름을 생각을 잘 못해내는 편이다.
그래서 위스키도 스펠링이 기억이 나지 않아 검색을 해보았는데 이게 웬걸..? 두 개가 나온다.
whisky whiskey
같은 위스키를 뜻하지만 어느 지역에서 부르느냐, 어느 지역에서 생산됐느냐에 따라 'e'가 붙는게 달라진다고 한다.
싱기방기 동방신기