네트워크 플로우

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

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