61.송유관 네트워크로 A 공급지에서 F 수요지까지 최대의 유량을 보내려고 한다. 최대유량은? (단, 링크의 화살표 방향으로만 송유가능하며 링크의 숫자는 용량을 나타냄)

① 12톤

정답: X

최대 유량 14톤에 못 미치는 값이라 A에서 F로 가는 길에 아직 남은 용량이 있다.

② 13톤

정답: X

13톤을 흘린 뒤에도 B→D·E→D·E→F 가운데 한 곳에 1톤 여유가 남아 더 보낼 수 있다.

③ 14톤

정답: O

A→B→D→F 4, A→B→E→F 4, A→C→E→D→F 5, A→C→B→E→D→F 1 → 14톤. D로 드는 B→D 4·E→D 6과 E→F 4가 모두 차서(4 + 6 + 4 = 14) 더 못 보낸다.

④ 15톤

정답: X

D로 들어가는 길(B→D 4·E→D 6)과 E→F 4를 더한 14톤이 막는 곳이라 15톤은 흐르지 못한다.

⑤ 16톤

정답: X

F로 들어가는 D→F 12와 E→F 4를 그냥 더한 값이다 — 그 앞에서 D로 들어올 수 있는 양이 10이라 막힌다.