[백준] No.9577 - 토렌트 (C++, 이분 매칭)

문제

 

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

9577번: 토렌트

 

풀이

 

solved.ac 난이도: Platium 4

 

두 집합의 대응 관계를 해결하는 이분 매칭 문제.

기본 적인 이분 매칭 문제를 해결하고 오면 이해하기 쉬울 것이다.

[백준] 축사 배정(2188)

 

 

이번 문제에서 두 집합으로 선택되는 것은 시간(A set)과 조각(B set)이다.

파일이 어떤 시더에게 있는지는 상관없이, 접속 시간에 해당 파일을 다운로드할 수 있는 여부가 중요하기 때문이다.

따라서 시더마다 정해진 접속 시간(start_time ~ end_time)에 해당 시더가 가지고 있는 조각을 모두 간선으로 연결해 주자.

 

단! 한번에 하나의 조각만을 다운 받을 수 있고 조각을 하나 다운로드하는 데는 1초의 시간이 걸린다.

즉, u 시더가 0~1초간 접속하고 1,2번 조각을 가지고 있다고 하자.

0초의 시점에서 1번 조각을 다운받는다면 1초가 되는 시점에서 다운로드가 끝나게 된다.

 

이제 2번 조각을 다운받으면 된다고 생각할 수 있지만, 1초가 되는 시점에서 u 시더는 접속을 종료한다.

2번 조각을 다운받으려면 1초의 시간이 걸리므로 u가 0~2초가 접속하지 않는 이상 조각을 더 이상 다운 받을 수 없다. 

그러므로 시더가 접속을 종료하는 시점에는 조각을 다운할 수 없음에 주의하자.

 

예제의 입력을 이분 그래프로 표현하면 다음과 같다.

3 2

1 3 1 1

0 3 3 1 2 3

 

 

 

코드