6136 : 최대 유량
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
네트워크 유량 네트워크에서 1번 노드(소스)에서 N번 노드(싱크)로 보낼 수 있는 최대 유량(Maximum Flow)을 구하는 프로그램을 에드몬드-카프 알고리즘을 사용해 작성하십시오.
입력 설명
첫째 줄에 정점 수 N (2 ≤ N ≤ 200)과 방향 간선 수 M (1 ≤ M ≤ 1,000)이 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v c (u에서 v로 가는 용량 c)가 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v c (u에서 v로 가는 용량 c)가 주어집니다.
출력 설명
소스 1번에서 싱크 N번까지의 최대 유량을 정수 형태로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2 10
1 3 5
2 4 4
3 4 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
9도움
BFS 탐색으로 잔여 용량이 있는 소스->싱크 증가 경로를 반복해 구하고, 최소 용량을 흘린 뒤 간선 역방향 용량을 갱신하는 처리를 증가 경로가 없을 때까지 루프로 반복하십시오.