티스토리 뷰

알고리즘 관련/알고리즘&이론

L-R flow

JASON 자손9319 2017. 8. 15. 17:50

http://blog.myungwoo.kr/111 와 http://koosaga.com/134 에서 많은 부분 참고하였습니다.




-간선에 lower_bound가 존재할 때 플로우를 흘릴 수 있는지 여부 확인


1. MCMF로 모델링


a->b로의 간선이 하한이 l 상한이 r일 때


a->b로 (l , -1)  , (r-l ,0)으로 두가지 간선을 만들어 준 뒤 MCMF 를 돌린다면 항상 -1이 있는 쪽으로 플로우가 강제된다.


이 때 cost를 확인하여 플로우를 흘릴 수 있는 지 여부를 확인해준다.


이 때의 maxflow는 flow를 확인하여 구할 수 있다.



2. 디닉을 사용하는 방법


새로운 소스와 새로운 싱크를 만든다.


기존 싱크-> 기존 소스로 capacity가 INF인 간선을 생성한다.


a->b로의 간선이 하한이 l 상한이 r일 때


a->새로운 싱크로 (l) , 새로운 소스->b로(l) , a->b로 (r-l) 간선을 만들어 준 뒤


새로운 소스-> 새로운 싱크로 maximum flow를 확인하여 l들의 합과 같은지 여부를 확인


이 때의 maxflow를 구하고 싶다면 기존 소스-> 기존 싱크로 가는 플로우를 찾을 수 있을 때 까지 계속 찾으면 된다.


댓글
댓글쓰기 폼