L-R flow

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를 구하고 싶다면 기존 소스-> 기존 싱크로 가는 플로우를 찾을 수 있을 때 까지 계속 찾으면 된다.

'알고리즘 관련 > 알고리즘&이론' 카테고리의 다른 글

좌표압축 기법  (0)	2017.09.19
deque를 이용한 다이나믹프로그래밍  (0)	2017.09.05
L-R flow  (0)	2017.08.15
트리에서 A와 B의 경로 사이에 C존재 여부  (0)	2017.07.11
다익스트라 알고리즘(Dijkstra's Algorithm)  (7)	2017.07.09
트리의 이심률,지름,반지름  (0)	2017.07.08