백준 6086번 최대 유량

문제 링크 : https://www.acmicpc.net/problem/6086

문제풀이

사용한 알고리즘 : Network Flow

강산님의 블로그 글을 참고하여 작성하였습니다.

(0) 생각

 네트워크 유량을 쓸 줄 아는가 묻는 문제였습니다.

 에드몬드 카프 알고리즘을 사용하여 풀이하였습니다.

(1) 코드 16~18

 각 노드간 간선을 저장할 vector 배열을 만들어 주었습니다.

 'c[i][j] : i->j 간선의 용량' ,

 'f[i][j] : i->j 간선의 유량' 이라고 설정해 주었습니다.

(2) 코드 43~78

 에드몬드 카프 알고리즘을 구현해줍니다.

 시작점(S)에서 도착점(T)까지 경로가 있는지 BFS로 탐색 해줍니다.

 경로가 존재 한다면, 해당 경로 상의 가장 작은 '용량-유량' 값을 구해주어, 이 값을 경로 상의 모든 간선에 더해줍니다.

 이때 구하고자 하는 답에도 해당 값을 더해줍니다.

 S ~ T 사이의 경로가 없을 때까지 반복해줍니다.