백준 11378 열혈강호 4

작성일 | In |

문제 링크

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

알고리즘

  • 이분 매칭

풀이

전체 벌점이 k다. 직원을 기준으로 희망 업무에 매칭시킨 후에, 추가로 매칭이 가능하다면 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
42
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):
    while k > 0:
        visited = [0] * (n+1)
        if sol(i):
            k -= 1
            count += 1
    
        else:
            break
        

print(count)