네트워크 최대 흐름
정수 용량 네트워크의 최대 흐름·최소 컷과 입력 간선별 흐름을 확인하세요.
예시값이 입력되어 있습니다. 바로 확인하거나 값을 바꿔 보세요.
입력은 브라우저에서 처리합니다. 새로고침하면 예시값으로 돌아갑니다.
사용 방법과 예시
Residual augmentation; max flow=min cut
기본 네트워크의 최대 흐름은 7이며 최소 컷 출발 측은 S와 A입니다. 입력 순서 간선 흐름은 4, 3, 4, 3입니다.
노드 30개·간선 100개 이하, 용량은 0~1000000 정수입니다. 최대 흐름 배분은 유일하지 않을 수 있으며 잔여 경로는 입력 순서로 탐색합니다.
자주 묻는 질문
최대 흐름에서 병렬 간선은 어떻게 처리하나요?
병렬·반대 방향 간선을 별개로 보존합니다. 입력 순서의 간선 행마다 용량과 흐름을 표시하며 자기 루프의 흐름은 0입니다.
최소 컷 출발 측 목록은 무엇을 뜻하나요?
흐름을 더 늘릴 수 없을 때 잔여 간선을 통해 출발점에서 도달 가능한 노드 집합입니다.
계산 기준과 참고 자료
- Princeton Algorithms: Maximum Flow
Residual augmentation; max flow=min cut