viewimage.php?id=3dae&no=24b0d769e1d32ca73cee86fa11d0283191de25edc716dfae8790c63e5d6bdc5a0af7d6346fd04f60dc7e45fe13989a7c49cf9f6c71cb43b59eb95a45d0



1019p 에 이분매칭의 속성을 설명할때 나오는 문구가 있음


"이 코드가 이용하려는 첫번째 속성은 이분매칭을 푸는 유량 네트워크에서 최대 유량은 O( V ) 로 정해져 있다는 것입니다. 

포드-풀커슨 알고리즘을 깊이 우슨 탐색으로 구현할때 큰 문제는 수행시간이 총 유량이 비례한다는 점 이었습니다.

하지만 이렇게 최대 유량이 재한되어 있는 경우 깊이 우선 탐색을 써도 문제가 없지요."



일단 내가 포드-풀커슨 에서 dfs를 쓰면 안되는이유를 이해한바로는


총 유량이 10만인 그래프에서 포드-풀커슨으로 깊이우선탐색을 썼다가 존나 최악의 케이스를 맞이해서 찾아낸 증가경로가 유량을 1밖에 (1이든 2든 암튼 매우 적은양) 못 더해줄경우


정말 최악의 케이스에서는 이걸 한번에 1씩, 10만번이나 해야되니까 ㅈ 되는거라고 알고있음.


근데 저기 위에 종만북에서는 "총 유량이 V로 정해져있으니까 괜찮음" 이러고 있는데. 


만약에 V가 10만이라면 똑같이 ㅈ되는건 매한가지 아님? 십만이라는 압박에서 벗어날수는 없을텐데 왜 저게 "깊이 우선탐색을 써도 문제가 없지요" 가 되는지 모르겠음..