74.출발지에서 도착지까지 파이프라인을 통해 가스를 보낼 경우 보낼 수 있는 최대 가스량(톤)은?

① 12

정답: X

c 쪽 길은 a→c 6에서, f 쪽 길은 d→f 3 + e→f 7 = 10에서 막혀 두 길을 합치면 12가 아니라 16이다.

② 13

정답: X

a→c→도착 6과 d→e→f→도착 7만 더하고 d→f 3을 빠뜨리면 13이 나온다.

③ 15

정답: X

15는 f→도착 용량인데, f로 들어오는 양은 d→f 3 + e→f 7 = 10뿐이다.

④ 16

정답: O

위 경로: 출발→a→c→도착은 a→c 6에서 막혀 6. 아래: f로 들어오는 d→f 3 + d→e→f 7 = 10(d는 a→d·b→d로 15까지 받는다). 합계 6 + 10 = 16 — a→c 6 + d→f 3 + e→f 7을 끊으면 16이라 더 못 보낸다.

⑤ 18

정답: X

a→c 6, d→f 3, e→f 7 세 링크를 끊으면 흐름이 막히므로 최대 16을 넘을 수 없다.