티스토리 뷰
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) (6) | 2017.07.09 |
트리의 이심률,지름,반지름 (0) | 2017.07.08 |
- TAG
- 네트워크 플로우
댓글
공지사항
- Total
- 315,368
- Today
- 35
- Yesterday
- 199
TAG
- MCMF
- 트리
- 이분 매칭
- MST
- dfs
- 그리디 알고리즘
- 수학
- disjoint-set
- BFS
- 다이나믹 프로그래밍
- KMP
- 힙
- 디닉
- 좌표 압축
- SCC
- 이분 탐색
- LCP array
- 네트워크 플로우
- 위상 정렬
- 세그먼트 트리
- lazy propagation
- 다익스트라
- partial sum
- lca
- 분할 정복
- 플로이드 워셜
- 라인 스위핑
- 에라토스테네스의 체
- Suffix Array
- brute force