오랜만에 다시 돌아온 MCMF

BOJ 7154 - Job Postings 링크
(2022.11.08 기준 P3)
(치팅하면 취업 못함)

문제

일자리와 학생이 주어지고, 학생의 학년과 매칭된 일자리의 선호 순위에 따라 만족도가 정해져 있다면, 모든 학생을 한 일자리에 배치시켰을 때의 가능한 최대 만족도의 합

알고리즘

만족도가 비용으로 하여금 유량을 흘리는 MCMF

풀이

문제 지문이 좀 모호하다.
요약해보자면, n개의 일자리와 m명의 학생이 있다. 일자리마다 배치될 수 있는 학생 수가 제한되어 있고, 학생마다 학년, 선호하는 일자리 4개가 주어진다. 그리고 학년별 선호하는 일자리의 우선순위에 따라 만족도가 정해져 있다.

문제 입력이 좀 알아먹기 힘들게 주어지는 감이 없지 않아 있는데, 이해하면 정말 간단한 문제다.
source - 학생 - 일자리 - sink 모양의 모델링을 하면 된다.
source와 모든 학생과 이어주고 용량은 1.
학생마다 선호하는 네 일자리와 간선을 잇고, 간선의 용량은 1, 비용은 정해져 있는 만족도로 정하자.
모든 일자리는 sink로 이어주고 용량은 배치 가능한 학생 수.

대충 그림으로 나타내면
위 모양이 되는 것이다.

코드

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

satisfaction = [[0, 0, 0, 0], [4, 3, 2, 1], [8, 7, 6, 5], [12, 11, 10, 9]] # 만족도

while True:
    n, m = map(int, input().split())
    if not n:
        break
    # 학생 : 0 ~ m - 1, 일 : m ~ n + m - 1, source : n + m, sink : n + m + 1
    source = n + m; sink = source + 1; length = sink + 1
    connect = [[] for _ in range(length)]
    capacity = [[0] * length for _ in range(length)]
    cost = [[0] * length for _ in range(length)]
    flow = [[0] * length for _ in range(length)]

    # 일 - sink
    for i in range(m, n + m):
        connect[i].append(sink)
        connect[sink].append(i)
        capacity[i][sink] = int(input())

    for i in range(m):
        # source - 학생
        connect[source].append(i)
        connect[i].append(source)
        capacity[source][i] = 1
        # 학생 - 일
        y, *c = map(int, input().split())
        for k in range(4):
            j = c[k] + m
            connect[i].append(j)
            connect[j].append(i)
            capacity[i][j] = 1
            cost[i][j] = satisfaction[y][k]
            cost[j][i] = -cost[i][j]

    # MCMF
    answer = 0 # 총 비용
    while True:
        # SPFA
        prev = [-1] * length
        distance = [inf] * length
        q = [False] * length
        queue = deque([source])
        distance[source] = 0
        q[source] = True
        while queue:
            here = queue.popleft()
            q[here] = False
            for there in connect[here]:
                # 최대 비용이니깐 cost를 빼서 비교 및 대입
                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
                    if not q[there]:
                        queue.append(there)
                        q[there] = True
        # sink로 가지 못했다면 break
        if prev[sink] == -1:
            break
        # 유량은 어차피 1
        here = sink
        while here != source:
            flow[prev[here]][here] += 1
            flow[here][prev[here]] -= 1
            answer += cost[prev[here]][here]
            here = prev[here]

    print(answer)

여담

Python3는 시간 초과가 난다. PyPy3로 제출해야 겨우 AC.
나도 C나 다시 공부해볼까..?