문제 링크
- http://icpc.me/11622
문제 출처
- 2015 CERC J번
사용 알고리즘
- BCC
- Hashing
풀이
여름학교 그래프 실습 때 tricon이라는 문제가 있었습니다. 친구에게 풀이를 들었지만 업솔빙이 끝날 때까지 결국 못 풀어서 다음날 조교님께 출처를 어쭈어봤고, 바로 이 문제였습니다.
근데 Juice Junctions 문제가 tricon보다는 훨씬 어려우니 먼저 tricon이라는 문제부터 봅시다.
tricon 문제
두 정점을 잇는 경로에서 임의의 한 간선을 제거해도 두 정점이 연결되어있다면 두 정점을 bi-connected라고 한다.
만약 두 정점을 잇는 경로에서 임의의 한 간선을 제거해도 두 정점이 bi-connected하면 두 정점을 tri-connected라고 하자.
그래프가 주어지면 tri-connected 관계인 정점의 쌍의 개수를 출력하라.
|V| <= 3000, |E| <= 4500
tricon 풀이
주어진 그래프 G에서 임의의 간선 하나를 없앤 새로운 그래프 G2를 생각해봅시다.
G2에서 bi-connected한 두 정점은 tri-connected관계일 가능성이 있습니다.
G2에서 두 정점이 bi-connected한지 판단하는 것은 G2의 단절선을 모두 제거한 그래프에서 두 정점이 연결되어있는지 확인하면 됩니다.
어떤 두 정점이 임의의 간선을 없앤 총 |E| 개의 새로운 그래프에서 모두 bi-connected하다면 그 두 개의 정점은 tri-connected합니다.
|E| 개의 새로운 그래프에서 단절선들을 모두 제거했을 때, 각 정점이 어떤 컴포넌트에 속하는지 기록을 해두자. 그러면 각 정점마다 |E| 개의 기록이 남아있습니다.
두 개의 정점에 존재하는 각각 총 |E| 개의 기록을 해싱등을 이용해 비교하면 tri-connected인지 빠르게 확인할 수 있습니다.
Juice Junctions
다시 Juice Junctions문제로 돌아옵시다.
모든 정점 쌍에 대해서 max-flow를 구해서 모두 더한 값을 출력하라고 합니다. 각 정점의 차수는 최대 3이므로 max-flow도 최대 3입니다.
max-flow를 구하는데 O(N)이 걸립니다. 모든 정점 쌍에 대해 이를 수행하면 O(N3), 너무 느리죠.
min-cut max-flow theorem에 의하면 min-cut과 max-flow는 같습니다. min-cut을 구하는 것으로 생각해봅시다.
연결되어있지 않은 정점 사이의 min-cut은 0입니다. 그러므로 각 컴포넌트들은 분리해서 생각해도 됩니다.
이 그래프에서는 어떤 두 정점을 잡아도 min-cut은 최소 1입니다.
tricon 문제와 비슷하게 단절선을 모두 제거해봅시다.
단절선을 제거해서 분리되는 두 정점 사이의 min-cut은 1이라는 사실을 알 수 있습니다.
단절선을 제거해서 생기는 컴포넌트들은 분리해서 생각해봅시다.
이 그래프에서는 어떤 두 정점을 잡아도 min-cut은 2 이상입니다. 아까 위에서 min-cut은 최대 3이라는 것을 알아냈기 때문에, min-cut이 2인지 3인지만 판단하면 됩니다.
tricon 문제에서 했던 것처럼 임의의 간선 하나를 없애고, 각 BCC마다 번호를 1, 2, …로 매겨줍시다.
다른 간선도 없애봅시다.
모든 간선에 대해 이 작업을 반복하면 tricon 문제처럼 tri-connected관계인 정점들을 찾아낼 수 있습니다.
그리고, tri-connected인 두 정점 사이의 min-cut이 3입니다.
결국, 두 정점이 tri-con이라면 min-cut은 3이 되고, bi-con이라면 2, 그냥 연결이 되어있다면 1, 연결이 되어있지 않다면 0입니다.
잘 구현해주면 됩니다.