76.다음과 같이 파이프라인 네트워크에서 S지점에서 F지점까지 가스를 보내려고 한다. ( )에 들어갈 내용으로 옳은 것은? (단, 링크의 숫자는 인접한 노드 간의 용량을 나타내며, 화살표 방향으로만 이동 가능함)

① ㄱ: 28, ㄴ: C→B, ㄷ: 2

정답: O

S→A→B→F 8, S→C→F 13, S→D→E→F 7 → 최대 유량 28. C→B를 3으로 열면 C에 남은 3이 B로 가지만 B→F 여유가 10 − 8 = 2라 2만 는다.

② ㄱ: 28, ㄴ: C→B, ㄷ: 3

정답: X

C→B로 3을 보내도 B→F에는 이미 8이 흘러 2만 더 받을 수 있다 — 늘어나는 양은 2다.

③ ㄱ: 28, ㄴ: C→E, ㄷ: 2

정답: X

C→E를 3으로 열면 E→F 여유가 10 − 7 = 3이라 2가 아니라 3이 는다.

④ ㄱ: 33, ㄴ: C→B, ㄷ: 3

정답: X

33은 F로 들어가는 링크 10 + 13 + 10을 그냥 더한 값이다 — 앞 구간 A→B 8·D→E 7에 막혀 28만 흐른다.

⑤ ㄱ: 33, ㄴ: C→E, ㄷ: 2

정답: X

지금 최대 유량은 33이 아니라 28이고, C→E를 열면 E→F 여유 3만큼 3이 는다.