구사과

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 인 간선을 포화 간선이라 정의..

BOJ SPOJ얼마 전 코포에 비슷한게 나와서 풀어본 문제. 집합 S가 주어졌을 때 XOR 값을 최대로 하는 부분집합의 XOR 값을 구하는 문제이다. 대부분의 경우에 2^maxbit - 1이 나올 거 같이 생겼지만, 어떠한 비트들이 다른 비트의 값에 종속적이기 때문에 실제로는 그렇지 않다는 것을 알 수 있다. 여기서 약간의 선형대수학 지식을 활용하자. 일단 주어진 수들을 modulo 2에서의 벡터로 생각할 수 있다. 선대에서 보통 이러한 경우가 나오면 row echelon form을 구해서 종속 관계를 추려내는데, 이것도 똑같이 하면 된다. 주어진 수로 이루어진 row echelon form을 구하는 방법은 다음과 같다. 숫자를 하나씩 하나씩 넣어가는데, 각 숫자에 대해서 가장 큰 비트부터 본다. 현재 ..