L-R Maxflow / Circulation Problem

ASC 1. Reactor Cooling

http://codeforces.com/problemset/gymProblem/100199/B

 

아무 circulation이나 찾으면 되고, 일반적으로 이것은 그냥 아무것도 흘려주지 않으면서 (...) 해결할 수 있다.

하지만 에지의 flow 량이 Fi, j <= Ci, j 형식이 아니라, Li, j <= Fi, j <= Ri, j라는 형태로 걸려있다. 즉 하한이 있어서 그럴 수는 없다. 

 

이를 해결하기 위해서는, 양변에 Li, j를 빼줘서 Fi, j <= Ri, j - Li, j 형태로 바꿔주는 것이 된다.

당연히 단순히 이것으로 되지는 않는데, 양변에 빼줬으니, 정점 j는 그 대신 Li, j만큼의 유량을 보장받아야 하고, 정점 i 역시 Li, j만큼의 유량을 흘려야만 한다.

고로, source와 sink를 만들어줘서, 이 정점에서 그 유량을 흘려주면 된다. max flow의 합이 Sum(Li, j)가 된다면, 모든 유량이 보장받았고, 해가 존재한다.

cpp : http://ideone.com/7INqrF

 

CF 704 D. Captain America

http://codeforces.com/problemset/problem/704/D

 

플로우 그래프를 만드는 과정은 생략. 

에지의 플로우 량에 lower bound가 붙은 것은 똑같은데, 이번엔 circulation이 아니라 maximum flow를 구해야 한다. 일단은 가능한지 여부만 판별한다고 생각해보자.

 

아까와 똑같은 방식으로 max flow를 구성하는데, 이 문제는 플로우 문제라, 원래 source와 원래 sink에서 무한한 유량을 제공할 수 없다는 문제점이 생긴다. 이를 해결하는 방식이 약간 괴랄한데, sink에서 source로 무한 용량의 간선을 생성하면, source는 무한히 제공, sink는 무한히 공급받으면서 똑같은 플로우 그래프를 구성할 수 있다. 이제 가능한지 여부는 판별할 수 있다.

플로우 양을 maximize해야 한다. 가능 여부를 판별한 플로우 그래프를 그대로 두고 (흘려준 걸 초기화하지 않고!)원래 source에서 원래 sink로 가는 max flow를 구해주면 된다. 이 max flow가 feasible solution임은 자명하다. 이게 maximum flow인건 augmenting path가 존재하지 않기 때문이다. (만약 optimal solution이 아니라고 가정하자. 실제 optimal solution과 symmetric difference를 취해주면 augmenting path를 찾을 수 있다.)

정점과 간선 개수가 N + M 정도이고 용량이 작으니 E^1.5 시간 안에 풀 수 있다. 

cpp : http://ideone.com/thLlg8

 

대전 2016 인터넷 예선 H 역시 704D랑 똑같은 방법으로 풀리며, 가능한지 여부만 판별하면 되니 조금 더 쉽다고 할 수 있다. http://blog.myungwoo.kr/111