[백준 11405번] 책 구매하기 (Python3)

import sys
from collections import *
def input(): return [*map(int,sys.stdin.readline().split())]

def SPFA():
  DP = [1e9]*K; DP[0] = 0
  dq = deque([0]); inq = [0]*K; parent = [0]*K
  while dq:
    now = dq.popleft()
    inq[now] = 0
    for next in adj[now]:
      c,w = graph[now][next]; w1 = DP[now]+w
      if c-flow[now][next] and w1<DP[next]:
        DP[next] = w1; parent[next] = now
        if not inq[next]:
          dq.append(next); inq[next] = 1
  if parent[M+1]:
    return parent

def solve():
  result = 0
  while parent:=SPFA():
    now = M+1; f = 1e9
    while now:
      last = parent[now]
      f = min(f,graph[last][now][0]-flow[last][now])
      now = last
    now = M+1
    while now:
      last = parent[now]
      flow[last][now] += f; flow[now][last] -= f
      result += f*graph[last][now][1]
      now = last
  return result

N,M = input(); K = N+M+2
A,B = input(),input()
data = [input() for i in range(M)]
graph = [[0]*K for i in range(K)]; adj = [[] for i in range(K)]
for i in range(1,M+1):
  adj[0].append(i); adj[i].append(0)
  graph[0][i] = B[i-1],0; graph[i][0] = 0,0
for i in range(1,N+1):
  adj[-i].append(M+1); adj[M+1].append(-i)
  graph[-i][M+1] = A[i-1],0; graph[M+1][-i] = 0,0
for i in range(M):
  for j in range(N):
    adj[i+1].append(-1-j); adj[-1-j].append(i+1)
    graph[i+1][-1-j] = 1e9,data[i][j]
    graph[-1-j][i+1] = 0,-data[i][j]
flow = [[0]*K for i in range(K)]
print(solve())

MCMF [백준 11408번] 열혈강호 5 (Python3) (tistory.com) 문제이다.

 

풀이를 설명하면,

1. source - 서점간에 간선을 만들고 용량은 B[i]이다.

2. 사람 - sink간에 간선을 만들고 용량은 A[i]이다.

3. 서점 - 사람간에 간선을 만들고 용량은 무한대, 비용은 data[i][j] 이다.

(모든 간선의 역방향에는 용량 0, 비용 음수의 간선을 만들어야한다)

4. 1,2,3의 그래프를 토대로 MCMF를 실행하여 최소 cost를 구한다.

 

간선만 정확하게 만든다면 간단한 문제이지만 간선을 만드는 과정에서 실수가 많이 나왔다. MCMF에 대해서 공부할 수 있는 좋은 문제였다.

 

 

오늘의 교훈) 다양한 MCMF 문제를 해결하자