6135 : 유량 기초 (BFS)
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
네트워크 유량(Network Flow) 모델에서 소스 S와 싱크 T가 주어집니다.
에드몬드-카프(Edmonds-Karp) 알고리즘은 증가 경로를 탐색할 때 BFS를 수행하여 항상 정점의 수가 최소인 최단 증가 경로를 탐색합니다.
네트워크 구조가 주어질 때, BFS를 단 1회 수행하여 찾게 되는 최초의 증가 경로 상에 흘릴 수 있는 최대 유량 값을 계산하는 프로그램을 작성하십시오.
에드몬드-카프(Edmonds-Karp) 알고리즘은 증가 경로를 탐색할 때 BFS를 수행하여 항상 정점의 수가 최소인 최단 증가 경로를 탐색합니다.
네트워크 구조가 주어질 때, BFS를 단 1회 수행하여 찾게 되는 최초의 증가 경로 상에 흘릴 수 있는 최대 유량 값을 계산하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 정점 수 N (2 ≤ N ≤ 100)과 간선 수 M (1 ≤ M ≤ 500)이 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v c (u에서 v로 가는 용량 c)가 주어집니다.
마지막 줄에는 소스 S와 싱크 T가 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v c (u에서 v로 가는 용량 c)가 주어집니다.
마지막 줄에는 소스 S와 싱크 T가 주어집니다.
출력 설명
최초의 BFS 탐색 증가 경로로 흘릴 수 있는 유량(최소 용량)을 출력합니다. 경로가 없으면 0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2 10
1 3 5
2 4 4
3 4 8
1 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
S에서 T로 가는 잔여 용량이 > 0 인 간선들만을 따라가는 BFS를 단 한 번 동작시킨 뒤, 기록된 부모 노드 추적으로 경로를 완성해 경로 간선들의 최소 잔여 용량을 반환하십시오.