1. 플로우 (Maximum s-t flow)


주로 유량이 정의된 그래프에서 특정 두 점 사이의 Maximum flow를 구하는 문제인데, 줄여서 플로우로 자주 불림
그래프 만드는 건 방법 없으니 알아서 잘 만들면 됨

자주 쓰는 BFS이용하는 Ford-Fulkerson은 Edmonds-Karp라고 함. 시간 복잡도는 O(VE^2)임.


Dinic은 O(V^2E), Unit capacity에서는 O(AE) (A = min{V^(2/3), E^(1/2)})임.

Unit capacity에서 이보다 빠른 알고리즘은 아직 없음


Push-relabel의 경우 정점을 큐에 넣어 순차적으로 방문하면 O(V^3)임.

쓰는 사람 말에 따르면 Gap heuristic을 추가로 적용해야 쓸만한 속도가 나온다고 함


Dinic의 Binary flow 변형 버전도 있는데 O(VE log U) (U는 간선 중 최대 유량의 크기)임


2. 이분매칭 (Maximum bipartite matching)


플로우의 한 경우로도 볼 수 있음. Dinic의 경우 Unit capacity이면 속도가 빨라지는데,
이분매칭 형태의 그래프에서는 Blocking flow를 O(V^(1/2)) 이상 찾지 않음이 증명되어 있음

좀 더 쓰기 좋게 정리한게 O(V^(1/2) E)의 Hopcraft-Karp 알고리즘


일반적으로 쓰는 DFS 기반 알고리즘은 O(VE)지만 짜기가 편해서 자주 씀


# 플로우 예제


+ Total flow: https://www.acmicpc.net/problem/6086

+ 상어의 저녁식사: https://www.acmicpc.net/problem/1671

+ 열혈 강호 3: https://www.acmicpc.net/problem/11377

+ PIGS: https://www.acmicpc.net/problem/1658

+ Avoiding the Apocalypse: https://www.acmicpc.net/problem/10319

+ Chess Competition: https://www.acmicpc.net/problem/5424

+ 도시 방문하기: https://www.acmicpc.net/problem/2316

+ 숫자판 만들기: https://www.acmicpc.net/problem/2365


# 이분 매칭


+ 열혈강호: https://www.acmicpc.net/problem/11375

+ 노트북의 주인을 찾아서: https://www.acmicpc.net/problem/1298

+ 범죄 파티: https://www.acmicpc.net/problem/13166

-> (별해) 2-SAT, 그리디

+ 주차장: https://www.acmicpc.net/problem/1348

+ INFORMACIJE: https://www.acmicpc.net/problem/2787
-> (별해) 그리디

+ 들쥐의 탈출: https://www.acmicpc.net/problem/2191

+ 비숍2: https://www.acmicpc.net/problem/2570

+ 바둑: https://www.acmicpc.net/problem/9495


# Maximum flow with demands


아래의 블로그 참고 (노란책에도 있다고는 하는데 따로 안봐서 ...)

-> http://koosaga.com/134

-> http://blog.myungwoo.kr/111


+ Rounding: https://www.acmicpc.net/problem/13569

+ Project Team (채점 불가): https://www.acmicpc.net/problem/13332

+ Captain America: http://codeforces.com/problemset/problem/704/D