ASC 1. Reactor Coolinghttp://codeforces.com/problemset/gymProblem/100199/B 아무 circulation이나 찾으면 되고, 일반적으로 이것은 그냥 아무것도 흘려주지 않으면서 (...) 해결할 수 있다.하지만 에지의 flow 량이 Fi, j 이를 해결하기 위해서는, 양변에 Li, j를 빼줘서 Fi, j 당연히 단순히 이것으로 되지는 않는데, 양변에 빼줬으니, 정점 j는 그 대신 Li, j만큼의 유량을 보장받아야 하고, 정점 i 역시 Li, j만큼의 유량을 흘려야만 한다.고로, source와 sink를 만들어줘서, 이 정점에서 그 유량을 흘려주면 된다. max flow의 합이 Sum(Li, j)가 된다면, 모든 유량이 보장받았고, 해가 존재한다.cpp..
유량 알고리즘과 테크닉들은 다른 분야에 비해서 자명하지 않고 어려운 증명들을 상당히 많이 사용한다고 느꼈다. 이러한 증명들을 알아둬야지만 상급 문제들을 풀 수 있다고 생각해서, 여러 중요한 정리들을 증명해 놓으려고 한다. 엄밀하게 잘 증명하려고 노력은 하고 있지만 잘 될지는 모르겠다. (지적 환영합니다) 정리 글하고 같이 보자. (정리에 없는 내용들도 있다.) 1) Edmonds-Karp Algorithm이 VE^2인 이유 Edmonds-Karp Algorithm이 VE^2인 이유를 증명하기 위해서는, 증가 경로를 많아야 VE번 찾는다는 것을 보이면 된다. BFS 한번이 O(E)이기 때문이다. 이 사실을 보이겠다. 정의 1. 간선의 capacity == 간선에 흐른 flow 인 간선을 포화 간선이라 정의..
- Total
- Today
- Yesterday