백준 11377번: 열혈강호 3 (Maximum flow)

문제링크:11377번: 열혈강호 3 (acmicpc.net)

11377번: 열혈강호 3

이 문제는 최대 유량을 이용해 푸는 문제이다. 기존의 풀었던 최대 유량 (또는 열혈강호 1) 에서 한가지 조건이 추가되는데, 기존에는 한 직원당 할 수 있는 일이 1개로 모두 같게 정해졌다면, 이번 문제는 모든 직원 N명중 K명은 특별히 2개의 일까지 할 수 있다는 조건이 추가된다.

 

내가 처음에 생각한 방법은 모든 직원에게 용량 2인 간선을 할당 해 주고, 기존의 최대 유량 알고리즘을 사용해 정답을 구한다. 그리고 마지막에 정답의 flow[source]를 보면서 source에서 직원까지 flow가 2인 직원들의 명수를 세고, 만약 2인 직원이 K보다 많다면 K명보다 많은 직원들이 2개의 일을 하고 있다는 뜻이므로 그 차이를 정답에서 빼 주었다. 그렇게 하면 2개의 일을 하던 직원 중, K명 내에 들지 못한 사람들을 1개씩 일하게 만들어 정답이 될 것이라 생각했다.

 

하지만 틀렸습니다를 받게 된다. 생각해 보니 만약 2개의 일을 하는 사람 중 K명 내에 들지 못한 직원 (A)가 (1, 2) 의 일을 2개 하고 있었다고 치자. 그런데 다른 직원 중 한명인 0개의 일을 하는 (B)직원은 (1,2)일을 할 수 있음에도 불구하고, 아까 (A)직원이 (1, 2)를 하고 있어서 이미 자리가 차지되어 0개의 일을 할수밖에 없었다. 그런데 아까 방식으로 답을 구하는 과정에서 (A)직원의 일을 하나 뺀 경우, (B)직원은 일을 (A)대신 일을 하나 처리해 줄 수 있음에도 위 방식은 이 경우를 카운트 하지 못한다.

 

만약 모든 직원으로 흘러가는 간선의 용량을 1과 2로 모든 경우를 나누어 계산한다면, 시간 복잡도가 기존의 최대유량 알고리즘 * (1000 C K) 로 매우 커지게 될 것이다. 이 문제를 해결하기 위해 사용한 방법은 먼저 기존의 풀었던 문제처럼 source에서 각 직원까지 용량 1인 간선을 할당하고, source에서 또다른 임의의 knode로 K만큼의 용량을 가진 간선을 할당한다. 여기서 knode는 특별히 2개의 일까지 할 수 있는 직원을 고르기 위한 임의의 노드이다. knode는 source노드처럼 작용하여 각 직원까지 용량 1인 간선을 할당하면, 가장 효율적인 방법으로 모든 직원 중 K명의 직원이 2가지 일을 할 수 있는 경우를 구할 수 있다.

import sys
from collections import deque

N,M,K = map(int,sys.stdin.readline().rstrip().split())

cap = [[0 for _ in range(N+M+3)] for _ in range(N+M+3)]
flow = [[0 for _ in range(N+M+3)] for _ in range(N+M+3)]

source = 0
knode = 1
sink = N+M+2

cap[source][knode] = K

for i in range(2,N+2):
    inputs = list(map(int,sys.stdin.readline().rstrip().split()))
    cap[source][i] = 1
    cap[knode][i] = 1
    for j in inputs[1:]:
        cap[i][j+N+1] = 1

for i in range(N+2,N+M+2):
    cap[i][sink] = 1
    
ans = 0

while 1:
    que = []
    que.append(source)
    parent = [-1 for _ in range(N+M+3)]
    parent[source] = source
    flag = 0
    while que:
        cur = que.pop()
        for end in range(N+M+3):
            if cap[cur][end] - flow[cur][end] > 0 and parent[end] == -1:
                que.append(end)
                parent[end] = cur
                if end == sink:
                    flag = 1
        if flag:
            break

    if parent[sink] == -1:
        break

    rfrom = sink
    while rfrom != source:
        rto = parent[rfrom]
        flow[rto][rfrom] += 1
        flow[rfrom][rto] -= 1
        rfrom = rto

    ans += 1

print(ans)

나는 처음 에드먼드 카프로 풀었다가 99%에서 계속해서 시간 초과가 떠서 최적화가 문제인가 하고 최대한 최적화를 해도 안되서 포드 풀커슨으로 했더니 바로 맞았습니다 를 받을 수 있었다. 생각해 보니 이 문제는 에드먼드 카프를 사용하는 것이 바보같은 짓이었다.

 

보통 최대 유량 알고리즘으로 augmenting path를 BFS로 찾는 에드먼드 카프 알고리즘을 사용한다. 이 문제는 각 간선의 용량이 1밖에 되지 않아 매우 작은 반면, 간선의 개수는 정말 대충 아주 rough하게 계산하면 (N+M+2)^2 = 2002^2 개로 매우 많다. 이럴 때에는 오히려 augmenting path를 DFS로 찾는 포드 풀커슨 알고리즘을 사용해야 시간 복잡도에서 이득을 볼 수 있다.

 

DFS로 찾는 포드 풀커슨 알고리즘의 시간 복잡도는 O((V+E)*F)  (F=최대 간선 용량) 이고, BFS로 찾는 에드먼드 카프 알고리즘의 시간 복잡도는 O(V*E^2) 이다. 일반적인 그래프의 경우에는 최대 간선 용량이 간선의 개수보다  크기 때문에 에드먼드 카프 알고리즘을 사용하지만, 이 문제는 반대의 조건이므로 포드 풀커슨을 사용해야 시간 내로 풀 수 있다.