[백준 11408번] 열혈강호 5 (Python3)

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

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

def solve():
  cnt = cost = 0
  while spfa:=SPFA():
    c,parent = spfa
    now = N+1
    while now:
      last = parent[now]
      flow[last][now] += 1; flow[now][last] -= 1
      now = last
    cnt += 1; cost += c
  print(cnt); print(cost)

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

MCMF 기본문제

네트워크 플로우와 알고리즘이 거의 비슷하지만, source-sink 경로를 구할 때, BFS로 아무 경로나 구하는 것이 아닌 최단거리로 구하는 것이 핵심이다.

최단거리는 역방향 플로우로 인해서 음의 가중치 간선이 존재하기 때문에 다 익스트라를 이용할 수 없고, 벨만포드 알고리즘을 이용해야 한다. 이때 벨만포드와 시간복잡도는 같지만 성능을 매우 개선시킨 SPFA라는 알고리즘을 이용할 수 있다. (참고 https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm)

 

SPFA와 MCMF를 공부할 수 있는 좋은 문제였다.

 

 

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