[네트워크 유량] Network Flow(최대 유량) 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 합니다. 일단 해당 알고리즘에서 사용하는 용어부터 설명하겠습니다. (네트워크 유량 알고리즘에서 간선은 두 정점을 잇는 파이프라고 생각하면 이해하기 쉽습니다.) 용량(Capacity) c(u, v)는 정점 u에서 v로 가는 간선의 용량(가중치)라고 합니다. 유량(Flow) f(u, v)는 정점 u에서 v로의 간선에 실제로 흐르는 유량을 의미합니다. 잔여 용량(Residual Capacity) 간선의 용량과 유량의 차이를 의미합니다. r(u, v) = c(u, v) - ..