목차
※ 쉽고 명확하게 풀이하실 수 있도록 문제 지문을 일부 수정했습니다. 실제 경진대회 문제 지문과 차이가 있는 점 참고 부탁드립니다.
언어별 메모리 제한/수행시간 제한(공통 적용)
- C/C++
메모리제한 512MB, 수행시간 2초
- Java
메모리제한 512MB, 수행시간 4초
- Python3
메모리제한 512MB, 수행시간 10초
Q4. 자동차 공장
알고리즘
- MCMF
- Dinic
힌트
간선과 도로는 같은 개념으로 이해하셔도 됩니다.
경로는 한 공장에서 다른 공장으로 갈 수 있는 경로입니다. 1개의 도로를 이용해도, 여러 개의 도로를 이용해도 경로입니다.
문제
현대모비스는 N개의 자동차 공장을 가지고 있다. 공장은 1번부터 N번까지 번호가 매겨져 있고, 모든 자동차는 1번 공장에서 조립이 시작되어서 N번 공장에서 자동차 제작을 마무리하고 출고한다.
공장 간의 관계는 N개의 정점과 M개의 간선을 가진 단방향 그래프로 나타낼 수 있다. 각 정점은 공장을 의미하고, 간선은 i번 공장에서 작업이 완료된 부품을 연결된 다음 공장으로 보내는 도로를 의미한다. 각 간선은 가중치를 가지고 있는데, 이는 그 도로를 이용해 보낼 수 있는 부품의 최대 개수를 의미한다.
예를 들어, 위 그림에서 N개의 공장이 있다고 가정하면, 각 정점은 공장을 의미하고 간선은 i번 공장에서 작업이 완료된 부품을 다음 공장으로 보내는 도로를 의미한다. 1번 공장에서 작업을 완료했다면 2번 공장 또는 3번 공장으로 보낼 수 있다.
다음 공장으로 부품을 보낼 때 가중치에 적힌 값만 최대로 보낼 수 있다.
예를 들어, 위 그림에서 1번 공장에서 작업이 완료된 부품을 3번 공장으로 최대 3개를 보낼 수 있습니다.
위 그림에서 한 개의 부품이 만들어질 때까지 경로와 한 번에 만들 수 있는 부품의 개수를 계산해보면 아래 표와 같습니다.
N개의 공장에서는 하나의 공장에서 출발하여 다시 해당 공장으로 돌아오는 사이클이 존재하지 않는다. 위 그림과 같이 1번 공장에서 출발하여 순서대로 2번 공장, 3번 공장을 지나 다시 1번 공장으로 돌아오는 경우는 없다는 것을 의미한다. 이를 DAG(Directed Acyclic Graph)라고 하며, 주어지는 그래프는 DAG를 만족한다.
현대모비스는 출고하는 자동차의 수를 늘리고 싶어 예산 S를 가지고 공장을 개선하려고 한다. u번 공장에서 v번 공장으로 작업 완료된 부품을 보내는 도로가 있다면 보내는 부품의 수를 1만큼 올릴 때 예산 1만큼 사용한다.
도로를 무작위로 개선한다면 엉망진창이 될 수 있기 때문에 아래 규칙을 모두 만족하는 도로만 만들 수 있다.
- 후보군 T에 속한 공장끼리만 간선을 만들 수 있다.
- 처음 주어진 공장에서 모든 도로의 길이를 1이라고 할 때, 1번 공장에서 출발하여 i번 공장으로 이동할 때 가능한 이동 거리 중 최댓값을 p_i라고 한다. 만약 1번 공장에서 i번 공장까지 이동하지 못하는 경우는 이동 거리가 0이라고 가정한다면, u번 공장과 v번 공장을 비교하여 P_u < P_v를 만족하거나 P_u = P_v, u < v를 만족하는 경우 u번 공장에서 v번 공장으로 부품을 보내는 도로를 만들 수 있습니다.
- u번 공장에서 v번 공장으로 부품을 보내는 경로를 만들려고 할 때, u, v 둘 다 후보군 T에 포함되어 있는 경우 u번 공장에서 v번 공장 또는 v번 공장에서 u번 공장으로 보내는 경로를 만들 수 있습니다.
예를 들어, 입력 예시 1번과 같이 2번 공장과 3번 공장 사이에 도로가 존재하기 때문에 예산 1을 소모하여 2번 공장에서 3번 공장으로 보내는 부품의 수를 1만큼 증가할 수 있다. 이렇게 공장을 개선시키면 최대로 출고할 수 있는 자동차의 수는 7대가 된다.
현재 주어진 예산 S를 최대한 사용해서 공장을 개선할 때, 최대로 출고할 수 있는 자동차 수를 구하시오.
