L-R flow


L-R flow란?


네트워크 플로우에서 각 간선에 흐를 수 있는 용량이 정해져 있듯이

무조건 흘러야 하는 하한이 정해지는 것이다.


이 하한을 어떻게 만족시켜야 할까? 

또는 하한을 만족시키면서 유량을 흘릴 수 있는지 어떻게 검사할까?



만약 a->b 간선을 e 라고 할 때, 이 간선에 흘러야 하는 하한을 l, 상한을 r이라고 하자.

또한 기존의 S,E 이외에 새로운 source 와 sink인 s,t 를 정의하자.




이떄 간선을 다음과 같이 구성하자


1. s -> b 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)

2. a -> t 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)

3. E -> S 로 cap = INF 인 간선 (①에서 S가 처음에 흘릴 유량에서 source가 아니기 때문에 무한한 유량을 제공하기 위함이다)

4. a -> b 로 cap = r-l 인 간선 (②에서 추가로 흐를 유량을 구하기 위함이다)





① 간선을 다음과 같이 구성한 후에 s에서 t로의 maxflow 를 구한다.

이 때의 maxflow == 간선 하한들의 합 과 같다면, 이 그래프는 하한을 만족하는 maxflow를 구할 수 있다는 것이다.



② 그 후에 한번 더 유량이 차있는 그래프 그대로 S에서 T로의 maxflow 를 구한다면, 하한을 만족한 후에 더 흘릴 수 있는 추가 유량을 구할 수 있다.



따라서 흐를 수 있는 유량은 maxflow(하한의 합)  + maxflow(추가 흐른양) 가 된다.

'알고리즘' 카테고리의 다른 글

문자열 해싱  (0) 2018.03.31
Min Path Cover in DAG  (0) 2018.03.31
L-R flow : 하한이 있는 플로우  (0) 2018.03.31
유량 테크닉  (0) 2018.03.31
codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26

+ Recent posts