68.출발지에서 도착지까지 유류를 운송하는 파이프라인에서 c → b 구간의 폐쇄를 고려하고 있다. 각각의 파이프라인 (ㄱ), (ㄴ)에서 운송 가능한 최대 유량은? (단, 링크의 숫자는 인접한 노드 간의 용량을 나타내며, 화살표 방향으로만 이동 가능함)

① ㄱ: 28, ㄴ: 27

정답: X

(ㄱ)은 출발에서 c·d로 가는 8 + 15에 a→b 7을 더한 30까지 흘릴 수 있어 28이 아니다.

② ㄱ: 28, ㄴ: 28

정답: X

c→b가 열린 (ㄱ)은 b에 3을 더 보내 30까지 흐른다 — 28은 c→b를 막은 (ㄴ)의 값이다.

③ ㄱ: 30, ㄴ: 24

정답: X

(ㄴ)에서도 b 7·c 12·e 9가 모두 도착까지 가서 28이 흐르므로 24보다 많다.

④ ㄱ: 30, ㄴ: 27

정답: X

(ㄴ)에서 c→도착 12를 채우려면 d에서 c로 4만 보내면 되고 d→e 9도 다 흘러 27이 아니라 28이다.

⑤ ㄱ: 30, ㄴ: 28

정답: O

(ㄱ) a→b 7·c→b 3이 b→도착 10, c→도착 12, d→e→도착 8로 30(상한: a→b 7 + 출발→c 8 + 출발→d 15 = 30). (ㄴ) c→b를 막으면 b는 7뿐이라 7 + 12 + 9 = 28.