알고리즘/그래프
2020. 7. 10.
네트워크 유량
그래프의 간선에 '용량'이라는 개념을 추가해 봅시다. 지금까지 많이 봐왔던 '비용'의 개념과는 조금 다릅니다. 어떤 간선 \(e\)가 30의 용량을 가지고 있다면, 최대 30의 유량이 흐를 수 있음을 말합니다. 용량이 있는 방향그래프에서, 시작점 \(S\)에서 끝점 \(T\)까지 흐를 수 있는 최대 유량(Maximum Flow)가 얼마인지 구하는 문제를 네트워크 유량 문제라고 합니다. 예를 들어 다음과 같은 그래프에서, 최대 유량은 60이고, 실해는 다음과 같습니다. 다양한 문제들을 유량 문제로 변환해 풀 수 있습니다. 예를 들어 이전 글에 썼던 이분 매칭의 경우, 다음과 같은 방식으로 변환하면 유량 문제로 바꿔서 풀 수도 있습니다. https://www.acmicpc.net/problem/11378 1..
