[백준 11407번] 책 구매하기 3 (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():
  cnt = 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
    cnt += f
  return cnt,result

N,M = input(); K = N+M+2
A,B = input(),input()
data1,data2 = [[input() for i in range(M)] for i in range(2)]
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] = data1[i][j],data2[i][j]
    graph[-1-j][i+1] = 0,-data2[i][j]
flow = [[0]*K for i in range(K)]
print(*solve(),sep="\n")

= [백준 11405번] 책 구매하기 (Python3) (tistory.com)

서점-사람 간의 간선에서 용량을 무한대가 아닌 C[i][j]로 두면 된다.