유량의 간선의 cap 1 증가 시켰을 때

말 그대로 하나만 1을 증가시켜서 dinic을 구한다. 

변화량이 많아봐야 1이다.

O(V+E) 


차있는 상태에서 한번 더 dinic 을 구하는 것.


유량 cap 1 감소시키는 것.

u->v 로 가는 간선에서, f == c 일때만 중요해.

u->v 에 풀 수 있다. (V+E) 

간선 우선순위를 정한다.



==> 응용하기


1,2,3,4 를 

mcmf 로 간선의 cost 2^1, 2^2, 2^3, 2^4 ...로 정해서  구한다.




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

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
acm-cicpc 수학정복  (2) 2017.09.15

+ Recent posts