[BOJ 19579] 물건 가져가기

문제

---

https://www.acmicpc.net/problem/19579

풀이

---

풀이가 너무나도 신기한 문제다.

1. source, sink, 1~N번 노드로 그래프를 구성한다.

2. i번째 물품의 기분의 변화치 $ t_i $가 양수이면 source에서 i번 노드까지 capacity $ t_i $로 이어준다.

3. i번째 물품의 기분의 변화치 $ t_i $가 음수이면 i번 노드에서 sink까지 capacity $ -t_i $로 이어준다.

4. s를 얻기 위해 e를 얻어야 한다면, s에서 e까지 capacity $ \infty $로 이어준다.

5. 최대 유량을 구한 후에, source에서 도달할 수 있는 물품들이 얻어야 하는 물품들이다.

증명은 SUAPC 2020 풀이에 간략하게 나와있다.

코드

---

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
happy = [int(sys.stdin.readline()) for _ in range(n)]

graph = [[] for _ in range(n + 2)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append([b, float('inf')])

for i in range(n):
    if happy[i] > 0:
        graph[0].append([i + 1, happy[i]])
    elif happy[i] < 0:
        graph[i + 1].append([n + 1, -happy[i]])

ans = 0
while True:
    prev = [-1] * (n + 2)
    queue = deque([(0, float('inf'))])
    while queue:
        cur, res = queue.popleft()
        
        for nxt, capacity in graph[cur]:
            if nxt == n + 1:
                res = min(res, capacity)
                prev[-1] = cur
                break
            
            if prev[nxt] == -1:
                prev[nxt] = cur
                queue.append((nxt, min(res, capacity)))

        if prev[-1] != -1:
            break
    
    if prev[-1] == -1:
        break

    ans += res
    nxt = n + 1
    while True:
        cur = prev[nxt]
        for i in range(len(graph[cur])):
            if graph[cur][i][0] == nxt:
                graph[cur][i][1] -= res
                if graph[cur][i][1] == 0:
                    graph[cur].remove([nxt, 0])
                break

        for i in range(len(graph[nxt])):
            if graph[nxt][i][0] == cur:
                graph[nxt][i][1] += res
                break
        else:
            graph[nxt].append([cur, res])

        nxt = cur
        if nxt == 0:
            break

sol = [0] * (n + 1)
for i, _ in graph[0]:
    if not sol[i]:
        sol[i] = 1
        queue = [i]
        while queue:
            cur = queue.pop()
            for nxt, _ in graph[cur]:
                if not sol[nxt]:
                    sol[nxt] = 1
                    queue.append(nxt)

sol[0] = 0
print(sol.count(1))
for i in range(1, n + 1):
    if sol[i]:
        print(i, end=' ')