백준 11377 열혈강호 3

작성일 | In |

문제 링크

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

알고리즘

  • 이분 매칭

풀이

이번 문제도 ‘열혈강호’ 응용 문제인데 그리 어렵지 않다. 이번에는 모든 직원이 아니라 일부 직원만 희망 업무를 두 개까지 맡을 수 있다.

따라서 직원 정점을 기준으로 먼저 직원마다 희망 업무에 하나씩 매칭시킨 후에, 매칭을 k번 더 시켜주면 된다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
lst = [[]]
for i in range(n):
    lst.append(list(map(int, input().split()))[1:])
    
task = [0] * (m+1)

def sol(x):
    if visited[x]:
        return False
    
    visited[x] = 1
    
    for i in lst[x]:
        if task[i] == 0 or sol(task[i]):
            task[i] = x
            return True

    return False


count = 0
for i in range(1, n+1):
    visited = [0] * (n+1)
    if sol(i):
        count += 1
        
for i in range(1, n+1):
    visited = [0] * (n+1)
    if sol(i):
        k -= 1
        count += 1
    
    if k == 0:
        break
        

print(count)