11378. 열혈강호 4

 

11378번: 열혈강호 4

---

이분 매칭 연습문제인 열혈강호 시리즈의 마지막 문제. 이번 문제는 조건이 더 까다로워졌다. 각 직원은 기본적으로 하나의 일을 할 수 있고, 벌점의 분배에 따라 일을 더 할 수 있다.

 

이분 매칭을 할 때 주의해야 할 점은, 일단 벌점을 생각하지 말고 직원당 한 번씩 매칭을 시도해야 한다는 점이다. 그렇지 않으면 앞에서 벌점을 다 써버려서 뒤의 직원들은 기본 1번의 매칭 기회조차 주어지지 않기 때문이다. 따라서 우선 한번씩 매칭한 다음, 남은 한도 내에서 추가로 매칭해야 정답을 얻을 수 있다.

 

네트워크 플로우 역시 마찬가지이다. 그래프로 모델링할 때 source와 직원 사이의 용량을 처음에는 ``1``로 설정하여 최대 유량을 구하고, 그 후 용량을 ``k`` 늘려서 구한 최대 유량 값을 더해야 정답을 얻을 수 있다.

---

일단 이분 매칭으로 풀었고, 네트워크 플로우로도 풀어보려 했는데 위에서 말한 조건을 빼먹는 바람에 1주일동안 맞왜틀.. ㅠㅠ