오랜만에 아주 간단한 MCMF 문제를 풀어보았다.

BOJ 8127 - Schools 링크
(2022.10.21 기준 P3)
(치팅 놉)

문제

n개의 학교가 1 ≤ m ≤ n인 m 번호를 하나씩 가지고 있다. 모든 숫자가 한번씩 사용될 수 있게 학교의 번호를 바꿔야 하고, ai ≤ m' ≤ bi를 만족하는 m' 번호로 바꾸는 비용은 ki * |m - m’| 이다.
이 때 드는 최소 비용 출력

알고리즘

source -> 학교 -> 번호 -> sink로 간선을 이어 최소 비용에 따른 유량을 살펴봐야 한다.

풀이

모델링은 간단하다.
source는 0, 학교는 1 ~ n, 번호는 n+1 ~ n*2, sink는 n*2+1
source와 모든 학교, 모든 번호와 sink를 용량 1인 간선으로 이어주고
각 학교의 가능한 번호의 범위로 하여금 용량은 1, 비용은 k * abs(원래 번호 - 바꾸려는 번호)로 간선을 이어주면 된다.
그리고 유량 흘리면 끝!

아주 간단한 MCMF 문제다.
MCMF 알고리즘을 모른다면 열혈강호 5 풀이를 참고해보자.

코드

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

def solve():
    # source : 0, school : 1 ~ n, number : n+1 ~ n*2, sink : n*2+1
    n = int(input())
    source = 0; sink = n * 2 + 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)]

    for school in range(1, n + 1):
        # source -> school
        connect[source].append(school)
        connect[school].append(source)
        capacity[source][school] = 1

        # school -> number
        m, a, b, k = map(int, input().split())
        for number in range(n + a, n + b + 1):
            connect[school].append(number)
            connect[number].append(school)
            capacity[school][number] = 1
            c = abs(m - number + n) * k # cost
            cost[school][number] = c
            cost[number][school] = -c

    # number -> sink
    for number in range(n + 1, n * 2 + 1):
        connect[number].append(sink)
        connect[sink].append(number)
        capacity[number][sink] = 1

    # MCMF
    result = [0, 0] # cost, flow
    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]:
                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

        # If there's no way to sink, BREAK
        if prev[sink] == -1:
            break
        
        # flow is ALWAYS 1
        here = sink
        while here != source:
            flow[prev[here]][here] += 1
            flow[here][prev[here]] -= 1
            result[0] += cost[prev[here]][here]
            here = prev[here]
        result[1] += 1

    # If flow is not n, print 'NIE'
    print(result[0]) if result[1] == n else print('NIE')

solve()

여담

주석을 영어로 하고 코드도 깔끔하게 했는데 코드가 보기 이뻐진 느낌..?
이쁜 코드가 최고지