ACM-ICPC 상 탈 사람

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