[백준 3640번] 제독 (Python3)

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

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

def solve():
  result = 0
  for _ in range(2):
    w,parent = SPFA()
    now = N*2
    while now!=3:
      last = parent[now]
      flow[last][now] += 1; flow[now][last] -= 1
      now = last
    result += w
  return result

while 1:
  try: N,M = input()
  except: break
  K = N*2+2
  graph = [{} for i in range(K)]
  for i in range(N):
    graph[i*2][i*2+1] = 0,1
    graph[i*2+1][i*2] = 0,0
  for _ in range(M):
    a,b,w = input()
    graph[a*2+1][b*2] = w,1
    graph[b*2][a*2+1] = -w,0
  flow = [[0]*K for i in range(K)]
  print(solve())

MCMF 응용문제

도시 왕복하기 2 [백준 2316번] 도시 왕복하기 2 (Python3) (tistory.com) 문제를 풀고오면 쉽게 해결할 수 있다.

도시 왕복하기 2 문제가 정점을 중복하지 않는 최대유량을 구하는 문제였다면, 이 문제는 정점을 중복하지 않는 MCMF를 구하는 문제이다.

정점을 두개로 분리하고, 간선을 만든 후 MCMF를 두 번 실행하면 결과를 얻을 수 있다.