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번이 된다.

소스 코드

No comments:

Post a Comment