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로 가는 플로우를 찾을 수 있을 때까지 계속 찾는다. 그럴듯 하고 실제로 된다. 왜까지는 모르겠다. 아마 초기에 circulation을 셋팅해놔도 max flow를 구할 때 optimality에 해가 되지 않는거 같다. 뭐 정해니까 맞을 거다 ㅠ

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

cpp : http://ideone.com/thLlg8

프로그래밍 콘테스트 챌린징 (노란책) 에도 L-R maxflow를 푸는 방법이 나오는데 위 방법이 더 나은거 같다. (사실 그거 짰다 틀렸다.. 내 잘못인거 같긴 하지만, 여전히 그 방법은 왜 되는지 잘 모르겠음) 

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