[BOJ 7616] 교실로 가는 길

문제

---

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

풀이

---

도시 왕복하기 2와 유사하게, flow network를 만들어 준다.

엣지 (a, b)가 여러 번 주어질 수 있음에 유의하자.

최대 flow를 구하고, k 미만이면 impossible을 출력한다.

k 이상이라면, graph 배열을 통해 2에서부터 경로를 역추적한다.

정말 오랜만에 한 번에 맞춘 문제이다.

코드

---

import sys
from collections import deque

idx = 0
while True:
    idx += 1
    k, n = map(int, sys.stdin.readline().split())

    if (k, n) == (0, 0):
        break

    graph = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]

    for j in list(map(int, sys.stdin.readline().split())):
        graph[1 + n][j] += 1
    
    for j in list(map(int, sys.stdin.readline().split())):
        graph[j + n][2] += 1

    for i in range(3, n + 1):
        for j in list(map(int, sys.stdin.readline().split())):
            graph[i + n][j] += 1
            graph[j + n][i] += 1

        graph[i][i + n] = 1
    
    ans = 0
    while True:
        prev = [-1] * (2 * n + 1)
        queue = deque([1 + n])
        while queue:
            cur = queue.popleft()
            
            if graph[cur][2]:
                prev[2] = cur
                break
            
            for nxt in range(3, 2 * n + 1):
                if (prev[nxt] == -1) and graph[cur][nxt]:
                    prev[nxt] = cur
                    queue.append(nxt)

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

        ans += 1
        nxt = 2
        while True:
            cur = prev[nxt]
            graph[cur][nxt] -= 1
            graph[nxt][cur] += 1
            nxt = cur
            if nxt == 1 + n:
                break

    print(f'Case {idx}:')
    if ans >= k:
        for _ in range(k):
            path = [2]
            while True:
                nxt = path[-1]
                if nxt == 1:
                    break

                for cur in range(1, n + 1):
                    if graph[nxt][cur + n]:
                        graph[nxt][cur + n] -= 1
                        path.append(cur)
                        break
            
            print(*reversed(path))

    else:
        print('Impossible')
    print()