[BOJ 10319] 좀비 아포칼립스

문제

---

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

풀이

---

아기자기한(?) 스토리에, 아이디어까지 요구하는 재밌는 문제였다.

처음으로 시간 개념이 도입되는데, 어차피 100 이하이므로 각 시각별로 노드를 만들어주면 된다.

도로 정보에 따라 엣지를 이어주고, 병원이 있는 노드는 sink로 이어주고, 현재 위치는 source로부터 엣지를 이어주면 된다.

제자리에 있을 수도 있으므로, 같은 위치에서 시간만 1초 흐른 후의 노드로 가는 엣지도 만들어야 한다.

그렇게 flow network를 구성하고 최대 유량을 구해주면 된다.

돼지 잡기처럼 인접 행렬로 구현하면 MLE가 떠서, 인접 리스트로 구현해야 된다.

코드

---

import sys
from collections import deque

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    i, g, s = map(int, sys.stdin.readline().split())
    k = n * (s + 1) + 2

    hospital = [0] * (n + 1)
    for __ in range(int(sys.stdin.readline())):
        hospital[int(sys.stdin.readline())] = 1

    graph = [[] for __ in range(k)]
    graph[0].append([(s + 1) * (i - 1) + 1, g])

    for __ in range(int(sys.stdin.readline())):
        a, b, p, t = map(int, sys.stdin.readline().split())
        for r in range(t, s + 1):
            graph[(s + 1) * (a - 1) + r - t + 1].append([(s + 1) * (b - 1) + r + 1, p])
    
    for x in range(n):
        if hospital[x + 1]:
            for y in range(s + 1):
                graph[(s + 1) * x + y + 1].append([k - 1, float('inf')])
        else:
            for y in range(s):
                graph[(s + 1) * x + y + 1].append([(s + 1) * x + y + 2, float('inf')])
    
    ans = 0
    while True:
        prev = [-1] * k
        queue = deque([(0, float('inf'))])
        while queue:
            cur, res = queue.popleft()

            for nxt, capacity in graph[cur]:
                if (nxt == k - 1) and capacity:
                    res = min(res, capacity)
                    prev[-1] = cur
                    break
                
                if (prev[nxt] == -1) and capacity:
                    prev[nxt] = cur
                    queue.append((nxt, min(res, capacity)))

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

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

    print(ans)