Monday, September 8, 2014

오늘 푼 플로우 문제들

1. CEOI 2002 5번

N * M 그리드에 0에 룩을 최대 몇 개 놓을 수 있는지의 문제이다.

이분 그래프를 구성하는데, 왼쪽에는 가로로 배치되는 룩의 구간들, 오른쪽에는 세로로 배치되는 룩의 구간들을 놓고 최대 매칭을 구하면 된다.
예를 들어, 가로로 배치되는 룩의 구간을 구한다고하면, (i, 1)~(i,m)까지 보면서 2를 만나면 번호를 늘려주고 아니면 계속 그 번호를 유지하면된다. (i, j)에서 가로로 배치되는 구간의 번호와 세로로 배치되는 구간의 번호에 용량 1을 지정해주면 된다. 당연히 소스랑 싱크에도 다 용량은 1로 지정해준다.

소스 코드

2. BOJ 1017

첫 번째 수와 짝지을 두 번째 숫자를 정한 다음에 나머지 숫자들에 대해서 어떤 2개(i번째와 j번째)가 더해서 소수가 된다면 i번째와 n+j번째에 용량을 1로 주는 이분 그래프를 구성해서 최대매칭을 구한 후, 그 값이 n-2(첫 번째 수와 두 번째 수를 제외하고 다 쌍이 생겼다는 말)인지 확인한다. n-2이면 정한 두 번째 숫자가 답이 될 수 있으므로 출력하면 끝.

소스 코드

3. Baltic Olympiad in Informatics 2008 6번

Min-cut 문제이다. 답이 되는 그래프의 꼴을 잘 생각해보면, 어떤 정점들을 기준으로 이분그래프로 분할되는 것을 알 수 있다. 각 정점들을 2개로 쪼개서, 사이에 각 톨게이트의 점거비용으로 유량을 준다. 나머지 간선들과, 소스 및 싱크에서 각 점들에 해당하는 유량들은 모두 무한대로 준다. 이렇게 그래프를 구성한 다음에 Maximum Flow를 돌려주면, 그 값이 최소 점거비용이 됨을 쉽게 알 수 있다. Minimum Cut Problem은 Maximum Flow와 동치임을 보여주는 문제이다. 여기서 문제는 점거해야하는 도시들을 출력해야하는 것이다.
Min-cut Vertex(그래프 상에서는 Edge지만, 정점을 2개로 쪼갰으니...)들을 구하기 위해서는
1) Source에서 residual(용량 - 흐른 유량)이 양수인 점들만을 bfs로 탐색하고 표시해둔다.
2) 표시된 점들과 표시 안된 점들 사이에 간선이 있는데, residual이 양수고 용량이 0이 아니라면 그 Edge가 Min-cut Edge이므로 색칠된 점들이 Min-cut Vertex가 된다.

나는 이 문제에서 점들을 이분화할 때, i번 톨게이트를 2*i-1번(들어오는 점)과 2*i번(나가는 점)으로 분리했다. 따라서 소스는 0번이 되고, 싱크는 2*n+1번이 된다.

소스 코드

20140908

DP, Greedy, Flow 문제들을 많이 풀어봤으니, 이제 2-SAT과 DS 문제들 위주로 풀어야겠다.
태규가 생각보다 DP와 그리디를 잘 푸는 것 같으니, 지훈이만 예전만큼만 감이 빨리 돌아오면 꽤나 만족스러운 결과를 얻을 수 있을 것 같다. 작년엔 명우랑 같이 연습(사실은 반강제적으로...)하다가 올해는 거의 혼자하는 상황에 오니까, 명우의 소중함을 깨닫게 되기도 한다ㅋㅋㅋ
인터넷 예선 때는 내가 교내 2위 안정권까지는 주도적으로 코딩을 하고, 팀워크를 맞춰서 뒷심을 발휘해보는 방향으로 가야겠다.