백준 6086. 최대 유량

https://www.acmicpc.net/problem/6086

6086번: 최대 유량

 

에드몬드 카프 알고리즘, network flow 라는 알고리즘을 사용하는데 처음 봤다.

현재 2023.01.05 난이도 골드4로 되어있는데, 난이도 기여 커멘트들을 보면 문제 데이터 수정이 계속 일어나서 처음에는 에드몬드 카프 알고리즘을 쓰지 않으면 못풀지만 지금은 단순 구현으로 풀수 있는것 같다. 

그래서 처음에는 플레티넘4 였는데 골드4까지 내려온듯 하다.

 

에드몬드 카프 알고리즘은 간단히 말하면 시작점에서 끝지점까지 도착할수 있는 최대 유량을 구하는건데, 핵심은 역방향으로도 용량을 할당

하고, 일정 방향으로 유량이 흐를때 역방향으로는 해당 크기 만큼 빼주는 것.

(나중에 다시 볼때 이 부분을 주의) 

 

또 주의할점이 용량을 책정할때 그냥 할당을 하면 안되고 더해야 한다.

capacity[a][b] = cap 

capacity[b][a] = cap

이건 틀리고

capacity[a][b] += cap

capacity[b][a] += cap

이건 맞다.

 

좀 찾아보니까 파이프가 중복으로 주어질수 있어서 그렇다는데..아직도 이 부분 이해가안간다.