B 항공사는 서울-상해 직항 노선에 50명의 초과예약 승객이 발생하였다… | [물류관리사] 14년 1회차 기출문제 상세 페이지

경유편으로 상해에 도착할 수 있는 최대 승객 수는 26명이다.
그림의 여유 좌석은 서울(S)→1이 10, S→2가 9, S→3이 17, 3→2가 20, 2→1이 15, 2→상해(F)가 11, 2→4가 13, 1→F가 7, 4→F가 8이다. 도착지 F로 들어오는 간선은 1→F 7, 2→F 11, 4→F 8뿐이므로 어떤 경우에도 26명을 넘을 수 없다.
실제로 그 상한이 달성된다. S→1로 7명을 보내 1→F의 7석을 채우고, S→2로 9명과 S→3→2로 10명이 노드 2에 모이면 그곳에서 2→F로 11명, 2→4→F로 8명을 내보낼 수 있다. 서울에서 출발하는 인원은 $7+9+10=26$ 명이며 사용한 간선(S→1 7≤10, S→2 9≤9, S→3 10≤17, 3→2 10≤20, 2→4 8≤13, 4→F 8≤8)이 모두 용량 이내이므로 26명 전원이 상해에 도착한다.
이처럼 최대유량 문제는 도착 노드로 들어오는 간선 용량의 합이 곧 상한이 되는지 확인하고, 그 값을 실제 경로 배분으로 채울 수 있는지 검증하는 순서로 푼다.