Mafia (BOI 2008)

https://www.acmicpc.net/problem/1210

1. 최소 코스트 구하기

문제를 뒤집어서 에지를 막을 때 일정한 코스트가 든다고 가정한다면, 이 문제는 Minimum Cut이라는 유명한 문제로 바뀐다는 것을 알 수 있다. Minimum Cut은 Maximum Flow와 동치임이 잘 알려져 있으므로 이러한 문제는 쉽게 풀 수 있다. (http://koistudy.net/?mid=prob_page&NO=1236)

다만, 애석하게도 이 문제에서는 정점을 막을 것을 요구하고 있기 때문에 이것만으로는 안 풀린다. 하지만 약간의 변형을 거치면 이 역시 Minimum Cut을 사용해서 쉽게 풀 수 있다.

정점을 In(i), Out(i)라는 두 정점으로 분할하자. In(i)는 이 정점으로 들어오는 간선들을 모두 모아놓은 정점이고, Out(i)는 이 정점으로 나가는 간선들을 모두 모아놓은 정점이다. 이런 식의 변형을 거치면 정점 i를 거쳐서 가는 경로는 모두 In(i) -> Out(i) 간선을 지나게 할 수 있다. 즉 정점을 막는 코스트를 간선을 막는 코스트로 쉽게 환원할 수 있다는 것이다.

이를 사용해서, 원래 간선은 무한의 코스트를 주고 (막히는 일이 없도록) In(i) -> Out(i) 로 가는 간선에만 정점을 막는 코스트를 부여하면, Maximum Flow를 사용해서 In(s) -> Out(e)로 가는 경로의 최소 코스트를 구할 수 있다. 시간 복잡도는 O(nm^2) 이지만, 공식 풀이에서는 유한한 코스트를 가진 간선이 N개 뿐이므로 실제로는 O(n^2m) 이라고 한다.

2. 막은 경로 출력하기

다만 실제로 출력해야 하는 것이 합이 아니라 막은 점 그 자체라는 것이 문제의 까다로운 부분 중 하나이다.

막은 경로는 다음과 같이 출력한다.

 * 1. In(s) 에서 residual이 0보다 큰 정점들을 모두 방문한다. 방문한 정점에 vis[i] = 1을 매긴다.

 * 2. In(i) -> Out(i) 로 가는 정점들 중, vis[In(i)] = 1이며 vis[Out(i)] = 0인 정점을 출력한다. 이 때 In(i) -> Out(i) 간선의 residual이 0임을 쉽게 알 수 있다.

알고리즘의 성립 원리는 다음과 같다.

어떠한 에지가 Min-Cut Edge라는 것은, 현재는 그 에지 때문에 플로우가 흐르지 않지만, 그 에지에 다시 어떠한 용량을 주면 플로우가 흐른다는 것을 의미한다.

때문에, vis[In(i)] = 0인 간선은 그 에지에 다시 용량을 주어도 플로우가 흐르지 않기 때문에 출력하면 안되며,

vis[In(i)] = 1, vis[Out(i)] = 1인 간선은 그 에지에 굳이 용량을 주지 않아도 플로우가 흐르기 때문에 출력하면 안된다.