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


긴글 ㅈㅅ



종만북에서


이분매칭 코드를 보여준다음에


이코드가 어떻게 이렇게 간결해질수 있냐면은 이분그래프의 두가지 속성을 이용하기 떄문이라고 그랫음


첫번째 속성은 이해되니까 패스하고


두번째 속성을 설명하는 텍스트는 아래와 같다


이 코드가 이용하는 또다른 속성은 증가경로를 찾기 위해 탐색을 하는 도중 B 에 포함된 정점에 도착했는데, 이 정점이 이미 매칭된 상황이라면 증가 경로의 다음 간선은 유일하게 결정된다는 것입니다. B에 속한 정점에서 나가는 간선은 싱크로 가는 간선 하나밖에 없는데, 현재 정점이 이미 매칭된 상황이면 이 간선에 잔여 용량은 남아있지 않을겁니다. 따라서 현재 정점으로 흘러오는 유량을 상쇄할수밖에 없는데, 현재정점으로 유량을 보내주는 정점은 현재 정점과 매칭된 정점밖에 없지요. 코드에서 dfs()에서 a에 인접한 정점 b에 대해, b가 이미 매칭된 상태라면 b에 인접한 정점들을 순회하는 대신 b에 매칭된 정점 bMatch[b] 로 곧장 재귀호출을 하는 부분은 이 속성을 이용한 것입니다.




초록색부분 문장이 뭔말인지 모르겠음. 어떤 의도를 설명하려고 하는건지 와닿지가 않음. 다음 간선은 유일하게 결정된다 가 뭔말임?

내가 새로운 증가경로 New 를 탐색하다 어떤 정점 b를 만났고, 이게 이미 매칭된상황이면

이 정점에서 싱크로 나가는간선은 하나밖에 없는데 그 간선은 이미 증가경로 Old가 사용중이라 잔여용량이 없다.

이제 이 정점 b는 New를 구하는데에 못쓰니까, 즉 b에서 막혔으니까 Old를 약간 수정해서 새로운 증가경로 New를 얻을수있도록 길을 터준다. 즉 흘러오는 유량을 상쇄한다는 말은 이런 의미이다.


.대충 이렇게 이해했는데 ‘증가경로의 다음간선은 유일하게 결정된다’ 가 어떤 의미인지 몰겠음.