Sean :: Dev

Network/Maximum Flow 유량그래프 : 간선의 weight가 정점에서 정점으로 보낼수있는 최대유량을 의미하는 그래프 최대유량 : 해당 간선을 통해 동시에 흘려보낼수있는 물의 최대치 이러한 유량그래프에서, Source정점에서 Sink정점까지 최대 얼마만큼의 유량이 지나갈수있는지에 관한 문제를 Network/Maximum Flow라고 한다. 아래와 같이, 수로(간선)에 1초마다 지날수있는 물의 최대치가 정의되어있다면, 수로는 자신의 용량이상의 물은 통과 시킬수없다. 따라서 결과적으로 통과할수있는 물의 최대량은 왼쪽은 2, 오른쪽은 4이다. 따라서 위의 그래프를 Maximum Flow(최대유량)으로 보내면 그 값은 7이다. 좌측값은 실제로 해당 간선에 흐른 유량(flow), 우측값은 해당 간선의 ..