[백준 2367번] 파티 (Python3)

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

def BFS():
  dq = deque([(0,1e9)])
  visited = [-1]*K
  while dq:
    now,f = dq.popleft()
    for next in graph[now]:
      if visited[next]<0 and (f1:=min(f,graph[now][next]-flow[now][next])):
        visited[next] = now
        if next==N+1:
          return visited,f1
        dq.append((next,f1))

def solve():
  while bfs:=BFS():
    visited,f = bfs
    now = N+1
    while now:
      last = visited[now]
      flow[last][now] += f; flow[now][last] -= f
      now = last

N,X,M = input(); K = N+M+2
graph = [{} for i in range(K)]
food = input()
for i in range(1,N+1):
  graph[0][i] = X
  graph[i][0] = 0
for i in range(1,M+1):
  graph[-i][N+1] = food[i-1]
  graph[N+1][-i] = 0
for i in range(1,N+1):
  _,*data = input()
  for d in data:
    graph[i][-d] = 1
    graph[-d][i] = 0
flow = [[0]*K for i in range(K)]
solve()
print(sum(flow[i][N+1] for i in range(K)))

최대유량 기본문제

 

풀이를 설명하면,

1. source-사람 사이에 용량 K의 간선을 만든다.

2. 각 사람이 만들 수 있는 음식에 대해서 용량 1의 간선을 만든다.

3. 음식-sink 사이에 용량 D[i]의 간선을 만든다.

(모든 간선은 용량 0의 역방향 간선을 갖는다)

4. 최대유량을 구한다.

 

 

오늘의 교훈) 다양한 최대유량 응용문제를 해결하자