9577. 토렌트

처참한 현장

4시간동안 맞왜틀 해서 화나서 쓴다.

9577번: 토렌트

---

회원들로부터 $n$개의 파일 조각을 다운로드하는 데 걸리는 최소의 시간을 구하는 문제이다. 어떤 파일 조각을 아무 회원으로부터 다운로드해도 되기 때문에, 회원에 대한 정보는 무시하고 파일 조각과 시간의 관계만 생각하자.

 

전형적인 이분 매칭 문제이다. 매칭하는 방향은 두 가지가 있는데, 나는 조각에 시간을 매칭했다. 각 조각을 다운로드할 시작 시각을 매칭하는데, 이때 시작 시간을 매칭하므로 그래프를 만들 때 $t_{2}$는 제외해야 한다.

 

그 후 각 조각마다 시간을 매칭하면 된다. 모든 조각에 시간을 매칭했을 경우 매칭한 값의 최댓값 + 1이 정답이고(시작 시간을 매칭했으므로), 매칭하지 못한 조각이 있을 경우 -1을 출력하면 된다.

 

# 맞왜틀 (중요)

그래프를 만들 때 시간을 중복해서 넣으면 안 된다.

ㅋㅋ 내 4시간이 이렇게 날아가다니..

 

다시 한 번 강조한다. 이분 매칭에서 그래프에 중복된 연결을 만들어서는 안 된다.

---

마음이 아프다