66.다음 그림에서 노드 간(c → b)의 용량이 3으로 새로 생성된다고 가정할 때, S에서 F까지의 최대 유량의 증가분은? (단, 링크의 숫자는 인접한 노드 간의 용량을 나타내며, 화살표 방향으로만 이동 가능함)

① 1

정답: X

c→b 3이 생기면 b→F 7을 a→b 4 + c→b 3으로 꽉 채워 증가분은 1이 아니라 3이다.

② 2

정답: X

새로 생긴 c→b 3을 다 흘릴 수 있다 — b→F 7에 여유가 3 있고 S→c 8에도 여유가 있다.

③ 3

정답: O

처음: b→F는 a→b 4, d→F는 6이라 10. c→b 3이 생기면 b→F = a→b 4 + c→b 3 = 7, d→F 6(a→d 3 + c→d 3)으로 13 → 증가분 13 − 10 = 3.

④ 4

정답: X

새 링크 용량이 3이고 b→F도 7에서 막혀 증가분은 3을 넘을 수 없다.

⑤ 5

정답: X

도착지로 들어가는 b→F 7과 d→F 6을 더해도 13이라 처음 10에서 5까지 늘 수 없다.