[BOJ 11377] 열혈강호 3

문제

---

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

풀이

---

열혈강호 2에서, 일을 2개까지 할 수 있는 직원의 수가 K명으로 한정됐다.

1. 직원 노드를 두 배로 늘린 그래프를 만들어 준다.

2. 1번 노드부터 N번 노드까지의 최대 매칭을 구한다.

3. 복제된 1번 노드부터 N번 노드에서 최대 매칭을 구하다가, 최대 매칭의 수가 K가 되면 멈춘다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if (b[nxt] == -1) or (not visit[b[nxt]] and dfs(b[nxt])):
            b[nxt] = cur
            return 1
    return 0


n, m, k = map(int, sys.stdin.readline().split())
graph = [0] * (2 * n)

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

b = [-1] * (m + 1)
ans1 = 0
for i in range(n):
    visit = [0] * (2 * n)
    ans1 += dfs(2 * i)

ans2 = 0
for i in range(n):
    visit = [0] * (2 * n)
    ans2 += dfs(2 * i + 1)
    if ans2 == k:
        break

print(ans1 + ans2)