백준 9577 토렌트

작성일 | In |

문제 링크

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

알고리즘

  • 이분 매칭

풀이

이분 매칭은 매칭 작업에 필요한 정점을 무엇으로 할 것인지 정하는 게 중요하다.

이 문제는 처음 정점을 뭘로 할지 몰라서 혼란스러웠다. 그래서 그냥 시간과 조각을 매칭시켜봤는데 성공했다.

그렇다. 그냥 해봤는데 문제가 풀렸다.

정점 만드는 작업을 제외하면 다른 이분 매칭 문제랑 다를 게 없는 쉬운 문제다.

전체 코드

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
43
44
45
46
47
48
49
import sys
input = sys.stdin.readline

def sol(x):
    if visited[x]:
        return False
    
    visited[x] = 1
    
    for i in time[x]:
        if part[i] == -1 or sol(part[i]):
            part[i] = x
            return True

    return False


t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    
    time_limit = 0
    time = [[] for _ in range(101)]
    for j in range(m):
        lst = list(map(int, input().split()))
        
        time_limit = max(time_limit, lst[1])
        for k in range(lst[0], lst[1]):
            time[k].extend(lst[3:])
         
    part = [-1] * (n+1)

    count = 0
    answer = -1
    for j in range(time_limit):
        visited = [0] * time_limit
        if sol(j):
            count += 1
            
        if count == n:
            answer = j
            break
    
    
    if answer == -1:
        print(answer)
    else:
        print(answer + 1)