백준 11376 열혈강호 2

작성일 | In |

문제 링크

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

알고리즘

  • 이분 매칭

이번 문제가 ‘열혈강호’ 문제와 다른 점은 각 직원이 희망 업무 중에서 두 개까지 맡을 수 있다는 것이다. 따라서 각 직원 정점을 기준으로 매칭 작업을 두 번씩 해주면 된다.

전체 코드

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
import sys
input = sys.stdin.readline

n, m = 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(2):
    for j in range(1, n+1):
        visited = [0] * (n+1)
        if sol(j):
            count += 1


print(count)