BOJ 11405 책 구매하기

모델링만 정리하자.

 

첫 줄은 사람수 n, 서점 수 m 이 주어진다. 

출발 노드는 0, 도착 노드는 n+m+1 으로 둔다. (따라서 노드 개수는 n+m+2 )

 

(1) 다음 행에 사람에 대한 정보가 주어진다.

1 부터 n 까지는 사람에 해당되는 노드 번호로 정했다.

출발 노드로부터 이 노드들에 '비용' 0 이고 간선 '용량'은 \(a_i\) 인 간선을 연결.

 

(2) 다음 행(3행)에 서점에 대한 정보가 주어진다.

n+1 부터 n+m 까지는 서점을 나타낸다. 비용은 0 이고 용량은 \(b_i\) 인 간선을 도착 노드에 연결.

 

(3) 뒤 따르는 m 개의 행에는 서점에서 각 사람(1~n)에게 배송할 때의 비용을 알려준다.  

주어지는 정보가 모델링의 순서와 바뀌어서 i 와 j 의 위치에 주의하자.

mcmf.link(j, n+i, c, INT_MAX);

 

 

언제나 그렇듯이 모델링이 끝나면  flow 문제는 루틴이다.