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를 구하고 싶다면 기존 소스-> 기존 싱크로 가는 플로우를 찾을 수 있을 때 까지 계속 찾으면 된다.
'알고리즘 관련 > 알고리즘&이론' 카테고리의 다른 글
| 좌표압축 기법 (1) | 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 |
