최대 유량

[백준 11377] 열혈강호 3 (C++)

11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 최대 유량 최대 유량 연습하기 열혈 강호 1번 문제와 동일하지만 2가지 일을 할 수 있는 직원의 수가 주어진다. 처음에 무식하게 직원 중에서 k명을 반복해서 뽑고 S에서 해당 직원으로 가는 용량을 2로 두어 매번 에드몬드 카프 알고리즘을 돌려볼까 하는 생각을 했었다. 당연히 그렇게 풀면 안된다. S에서 직원으로 일을 할 수 있는 에너지를 보낸다고 생각했다. 그리고 S말고 다른 정점에서 직원들에게 K만큼의 에너지를 1씩 분..

[백준 2188] 축사 배정 (C++)

2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 최대 유량 주어진 입력을 그래프로 나타내 보았다. 소는 자신이 원하는 축사로만 이동할 수 있음을 나타냈다. 축사에는 소를 1마리만 들일 수 있으므로 축사에서 목적지로 1마리만 보낼 수 있다고 생각해도 무방하다. 위 그래프의 정점의 개수는 12개이다. 시작점이 0번, 끝점이 1번. 소들은 2번부터 6번까지, 축사는 7번부터 11번의 번호를 가지게 된다. 그래프는 단방향 그래프지만 음수 유량을 통해서 유량 상쇄를 구현하기 위해서 그래프는 모두 양방향으로 연결해 준다. ..