BOJ 15562 - 네트워크

image.png

웰노운컵 문제인데 솔직히 문제가 이해가 잘 안된다.

어쨌든 정답은 $\sum \text{Max}(0, out_i-in_i)$ 이다.

왜냐면 $x \rightarrow y \rightarrow z$가 있다면 최대한 $y$ 를 중간에서 삭제해주며 $x \to z$ 로 가게만들 수 있기 때문이다.

Tags:

Categories:

Updated:

Comments